En Seoul Science High School hay $N$ profesores y $N$ estudiantes. Cada estudiante compró $N$ flores porque mañana es el Día del Profesor en Corea. Sin embargo, uno de los estudiantes abandonó la escuela y ahora solo quedan $N-1$ estudiantes.

Los profesores son muy envidiosos, por lo que pondrán una calificación F a un estudiante si reciben de él menos flores que los demás profesores. Por tanto, cada profesor debe recibir exactamente $N-1$ flores. Un estudiante solo puede dar flores a los profesores que le han enseñado, y sabes qué estudiantes han estudiado con qué profesores.

Younghun es estudiante de Seoul Science High School y necesita tu ayuda para organizar este evento.

Entrada

La primera línea contiene dos enteros $N$ y $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), que describen el número de profesores y el número de pares (estudiante, profesor) en los que el estudiante ha estudiado con el profesor.

Las siguientes $M$ líneas describen las relaciones: la $j$-ésima línea contiene dos enteros $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), que indican que el estudiante $s_j$ puede dar flores al profesor $t_j$. Se garantiza que todos los pares son distintos.

Salida

Si es imposible dar a todos los profesores el mismo número de flores ($N-1$ flores), imprime un único número $-1$ en la primera línea.

En caso contrario, tu programa debe imprimir $M$ líneas. En la $j$-ésima línea debe haber un único entero que indique el número de flores que el estudiante $s_j$ dio al profesor $t_j$.

Si hay varias respuestas posibles, puedes imprimir cualquiera de ellas.

Ejemplos

Entrada 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

Salida 1

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

Entrada 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

Salida 2

-1