An der Seoul Science High School gibt es $N$ Lehrer und $N$ Schüler. Jeder Schüler hat $N$ Blumen gekauft, weil morgen in Korea der Tag der Lehrer ist. Allerdings hat einer der Schüler die Schule verlassen, sodass jetzt nur noch $N-1$ Schüler an der Schule sind.

Die Lehrer sind sehr neidisch und geben einem Schüler die Note F, wenn sie von ihm weniger Blumen erhalten als andere Lehrer. Daher soll jeder Lehrer genau $N-1$ Blumen erhalten. Ein Schüler darf nur Lehrern Blumen geben, die ihn unterrichtet haben, und du weißt, welche Schüler bei welchen Lehrern gelernt haben.

Younghun ist Schüler der Seoul Science High School und braucht deine Hilfe bei der Organisation dieser Veranstaltung.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $N$ und $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), die die Anzahl der Lehrer und die Anzahl der Paare (Schüler, Lehrer) beschreiben, bei denen der Schüler von dem Lehrer unterrichtet wurde.

Die nächsten $M$ Zeilen beschreiben die Beziehungen: Die $j$-te Zeile enthält zwei ganze Zahlen $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), die angeben, dass der $s_j$-te Schüler dem $t_j$-ten Lehrer Blumen geben darf. Es ist garantiert, dass alle Paare verschieden sind.

Ausgabe

Falls es unmöglich ist, allen Lehrern gleich viele Blumen ($N-1$ Blumen) zu geben, gib in der ersten Zeile eine einzelne Zahl $-1$ aus.

Andernfalls soll dein Programm $M$ Zeilen ausgeben. In der $j$-ten Zeile soll eine einzelne ganze Zahl stehen, die die Anzahl der Blumen angibt, die der $s_j$-te Schüler dem $t_j$-ten Lehrer gegeben hat.

Falls es mehrere mögliche Antworten gibt, darfst du eine beliebige davon ausgeben.

Beispiele

Eingabe 1

6 12
1 3
1 4
1 5
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 4
5 6

Ausgabe 1

1
0
5
5
1
2
4
3
0
3
1
5

Eingabe 2

6 12
1 2
1 3
1 4
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 5
5 6

Ausgabe 2

-1