Há $N$ professores e $N$ alunos na Seoul Science High School. Cada aluno comprou $N$ flores porque amanhã é o Dia do Professor na Coreia. No entanto, um dos alunos abandonou a escola, e agora restam apenas $N-1$ alunos.

Os professores são muito invejosos, por isso darão uma nota F a um aluno se receberem dele menos flores do que os outros professores. Portanto, cada professor deve receber exatamente $N-1$ flores. Um aluno só pode dar flores aos professores que o ensinaram, e sabes quais alunos estudaram com quais professores.

Younghun é aluno da Seoul Science High School e precisa da tua ajuda para organizar este evento.

Entrada

A primeira linha contém dois inteiros $N$ e $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), que descrevem o número de professores e o número de pares (aluno, professor) em que o aluno estudou com o professor.

As próximas $M$ linhas descrevem as relações: a $j$-ésima linha contém dois inteiros $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), indicando que o aluno $s_j$ pode dar flores ao professor $t_j$. É garantido que todos os pares são distintos.

Saída

Se for impossível dar a todos os professores o mesmo número de flores ($N-1$ flores), escreve um único número $-1$ na primeira linha.

Caso contrário, o teu programa deve escrever $M$ linhas. Na $j$-ésima linha deve haver um único inteiro que indique o número de flores que o aluno $s_j$ deu ao professor $t_j$.

Se houver várias respostas possíveis, podes escrever qualquer uma delas.

Exemplos

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

Saída 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

Saída 2

-1