在克罗地亚有 $N$ 个城市，由 $E$ 条双向道路连接。两家大型连锁餐饮集团最近达成了一项市场瓜分协议。在每条道路的中点，将有且仅有一家集团获得开设餐厅的特权。

为了确保市场公平瓜分，对于每个城市，在与其相连的道路上，必须至少各有一家属于两家集团的餐厅。然而，有些城市只有一条道路相连，或者根本没有道路相连，对于这些城市来说，同时拥有两家集团的餐厅是不可能的。这些城市注定只能光顾其中一家集团，或者需要走得更远一些。

编写一个程序，为每条道路确定应该由哪家集团在此开设餐厅，以满足上述要求。

输入格式

第一行包含两个整数 $N$ 和 $E$（$1 \le N, E \le 100\,000$），分别表示城市的数量和道路的数量。

接下来的 $E$ 行，每行包含两个整数。每行描述一条道路。整数 $A_i$ 和 $B_i$（$1 \le A_i, B_i \le N$ 且 $A_i \neq B_i$）表示连接城市 $A_i$ 和 $B_i$ 的一条道路。

输入中不会存在连接相同城市的多条道路（即无重边）。

输出格式

如果无法公平地分配道路，输出的第一行也是唯一一行应该包含 0。

否则，输出恰好 $E$ 行，每行对应一条道路，顺序与输入中的顺序相同。第 $i$ 行如果由第一家集团获得该道路的建设权，则输出 1；如果由第二家集团获得，则输出 2。

注意：如果解不唯一，您可以输出任意一个合法解。

子任务

本题的测试用例被分成了若干个测试点。每个测试点包含一个或多个测试用例。为了获得该测试点的分数，必须正确解答该测试点中的所有测试用例。

您无需担心输入输出中的测试点处理，系统会自动为您处理。请严格遵守输入/输出格式！

对于 $60\%$ 的数据，满足 $N \le 1000$，$E \le 5000$。

样例

输入样例 1

5 6
1 2
2 3
3 1
3 4
1 4
4 5

输出样例 1

1
2
1
2
2
1

输入样例 2

7 7
1 2
2 3
3 1
4 5
5 6
6 7
7 4

输出样例 2

0

输入样例 3

77777 4
1 2
1 3
1 4
1 5

输出样例 3

1
2
2
2