Problem Description

Given an undirected graph with $N$ nodes and $E$ edges.

You can color these $E$ edges either red or blue. Find a coloring method such that every node with a degree of at least 2 is connected to edges of both colors. If there is no solution, output $0$.

Input Format

The first line contains two integers $N$ and $E$.

The following $E$ lines each contain two integers $A_i$ and $B_i$, indicating that the $i$-th edge connects nodes $A_i$ and $B_i$. The data guarantees that there are no duplicate edges.

Output Format

If there is no solution, output $0$.

Otherwise, output $E$ lines, each indicating the color of an edge (corresponding to the input order). Use $1$ for red and $2$ for blue.

If there are multiple solutions, output any one of them.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
2
1
2
2
1

Sample Input #2

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

Sample Output #2

0

Sample Input #3

77777 4
1 2
1 3
1 4
1 5

Sample Output #3

1
2
2
2

Notes

[Data Range and Constraints]

This problem uses subtask testing.

• Subtask 1 (78 pts): $N \le 1000$, $E \le 5000$.
• Subtask 2 (52 pts): No additional constraints.

For $100\%$ of the data, $1 \le N, E \le 10^5$.

[Hints and Notes]

Feel free to hack the custom Special Judge via private message or posting.

Translated from COCI 2009-2010 CONTEST #7 Task 6 RESTORAN.

This problem's score is set according to the original COCI, with a full score of $130$.

见题面 Input 部分

见题面 Output 部分