首尔科学高中有 $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