首爾科學高中有 $N$ 位老師和 $N$ 位學生。因為明天是韓國的教師節，每位學生都買了 $N$ 朵花。然而，其中一位學生退學了，現在學校裡只剩下 $N-1$ 位學生。

老師們非常愛嫉妒，因此，如果某位老師收到某個學生送的花比其他老師少，就會給這個學生評 F。因此，每位老師都應恰好收到 $N-1$ 朵花。學生只能給教過自己的老師送花，而你知道哪些學生曾向哪些老師學習。

Younghun 是首爾科學高中的學生，他需要你幫忙組織這次活動。

輸入格式

第一行包含兩個整數 $N$ 和 $M$（$2 \le N \le 100 000$，$1 \le M \le 200 000$），分別表示老師的人數，以及學生曾向老師學習過的（學生，老師）數對的數量。

接下來的 $M$ 行描述這些關係：第 $j$ 行包含兩個整數 $s_j$、$t_j$（$1 \le s_j \le N-1$，$1 \le t_j \le N$），表示第 $s_j$ 位學生可以給第 $t_j$ 位老師送花。保證所有數對互不相同。

輸出格式

如果無法讓所有老師收到同樣數量的花（$N-1$ 朵），在第一行輸出一個數 $-1$。

否則，你的程式應輸出 $M$ 行。第 $j$ 行應包含一個整數，表示第 $s_j$ 位學生送給第 $t_j$ 位老師的花的數量。

如果有多個可行答案，你可以輸出其中任意一個。

範例

輸入格式 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

輸出格式 1

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

輸入格式 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

輸出格式 2

-1