首爾科學高中有 $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