题目描述

首尔科学高中（Seoul Science High School）有 $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$ 位老师的花的数量。

如果存在多个可能的答案，输出其中任意一个即可。

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
0
5
5
1
2
4
3
0
3
1
5

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

-1

提示

翻译由 DeepSeek 完成