P8076 [COCI 2009/2010 #7] RESTORAN

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$.

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.

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.

**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](https://www.luogu.com.cn/paste/omg15jba) by private message or by making a post. **Translated from [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 6 RESTORAN_.** **The score settings follow the original COCI problem, with a full score of $130$.** Translated by ChatGPT 5