질투하는 선생님

한국과학기술원 부설 한국과학영재학교(KSA)에는 $N$명의 선생님과 $N$명의 학생이 있다. 내일이 스승의 날이라서 학생들은 각자 $N$송이의 꽃을 샀다. 그런데 학생 한 명이 학교를 그만두는 바람에 이제 학생은 $N-1$명만 남았다.

선생님들은 매우 질투가 많아서, 어떤 학생에게 다른 학생들보다 적은 수의 꽃을 받으면 그 학생에게 F 학점을 준다. 따라서 모든 선생님은 정확히 $N-1$송이의 꽃을 받아야 한다. 학생은 자신을 가르친 선생님에게만 꽃을 줄 수 있고, 어느 학생이 어느 선생님에게 배웠는지는 주어진다.

승현이는 KSA의 학생이며, 이 행사를 준비하는 데 당신의 도움이 필요하다.

첫 번째 줄에는 선생님의 수와 (학생, 선생님) 쌍의 수를 나타내는 두 정수 $N$과 $M$이 주어진다.

다음 $M$개의 줄에는 관계가 주어진다. $j$번째 줄에는 두 정수 $s_j$, $t_j$가 주어지며, 이는 $s_j$번째 학생이 $t_j$번째 선생님에게 꽃을 줄 수 있다는 뜻이다. 모든 쌍은 서로 다르다.

모든 선생님에게 같은 수의 꽃($N-1$송이)을 줄 수 없다면 첫 번째 줄에 $-1$을 출력한다.

그렇지 않으면 $M$개의 줄을 출력한다. $j$번째 줄에는 $s_j$번째 학생이 $t_j$번째 선생님에게 준 꽃의 수를 나타내는 정수 하나를 출력한다.

가능한 답이 여러 개라면 아무 것이나 출력해도 된다.

• $2 \le N \le 100\,000$
• $1 \le M \le 200\,000$
• $1 \le s_j \le N-1$ ($1 \le j \le N$)
• $1 \le t_j \le N$ ($1 \le i \le N$)