Il y a $N$ enseignants et $N$ élèves à la Seoul Science High School. Chaque élève a acheté $N$ fleurs, car demain est la journée des enseignants en Corée. Cependant, l'un des élèves a quitté l'école, et il ne reste maintenant que $N-1$ élèves.

Les enseignants sont très jaloux : ils donneront donc la note F à un élève s'ils reçoivent de lui moins de fleurs que les autres enseignants. Par conséquent, chaque enseignant doit recevoir exactement $N-1$ fleurs. Un élève ne peut offrir des fleurs qu'aux enseignants qui lui ont enseigné, et vous savez quels élèves ont suivi les cours de quels enseignants.

Younghun est élève à la Seoul Science High School et a besoin de votre aide pour organiser cet événement.

Entrée

La première ligne contient deux entiers $N$ et $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), qui décrivent le nombre d'enseignants et le nombre de couples (élève, enseignant) dans lesquels l'élève a suivi les cours de l'enseignant.

Les $M$ lignes suivantes décrivent les relations : la $j$-ième ligne contient deux entiers $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), indiquant que le $s_j$-ième élève peut offrir des fleurs au $t_j$-ième enseignant. Il est garanti que tous les couples sont distincts.

Sortie

S'il est impossible de donner à tous les enseignants le même nombre de fleurs ($N-1$ fleurs), affichez un unique nombre $-1$ sur la première ligne.

Sinon, votre programme doit afficher $M$ lignes. La $j$-ième ligne doit contenir un unique entier indiquant le nombre de fleurs que le $s_j$-ième élève a données au $t_j$-ième enseignant.

S'il existe plusieurs réponses possibles, vous pouvez afficher n'importe laquelle.

Exemples

Entrée 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

Sortie 1

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

Entrée 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

Sortie 2

-1