Problem Description

You are given an undirected graph with $N$ nodes and $E$ edges.

Now you may color these $E$ edges red or blue. Find a coloring such that every node whose degree is at least $2$ is incident to edges of both colors. If there is no solution, output $0$.

Input Format

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

The next $E$ lines each contain two integers $A_i, B_i$, meaning the $i$-th edge connects nodes $A_i$ and $B_i$. The testdata guarantees that there are no multiple edges.

Output Format

If there is no solution, output $0$.

Otherwise, output $E$ lines. Each line gives the color of an edge (in the same order as the input). Use $1$ for red and $2$ for blue.

If multiple solutions exist, output any one of them.

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

1
2
1
2
2
1

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

0

77777 4
1 2
1 3
1 4
1 5

1
2
2
2

Hint

Constraints

This problem uses bundled testdata.

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

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

Hints and Notes

You are welcome to hack the self-written Special Judge by private message or by making a post.

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

The score settings follow the original COCI problem, with a full score of $130$.

Translated by ChatGPT 5