P8076 [COCI 2009/2010 #7] RESTORAN

给定一张含 $N$ 个结点、$E$ 条边的无向图。 现可将这 $E$ 条边染成红色或蓝色。求一种染色方式，使得所有度数不小于 $2$ 的结点都能连接两种颜色的边。若无解，则输出 $0$。

第一行，两个整数 $N,E$。 接下来的 $E$ 行，每行两个整数 $A_i,B_i$，表示第 $i$ 条边连接 $A_i,B_i$ 两个结点。数据保证不存在重边。

若无解，请输出 $0$。 否则输出 $E$ 行，每行输出一条边所染成的颜色（与输入顺序对应）。红色用 $1$ 表示，蓝色用 $2$ 表示。 如果存在多解，请输出任意一种。

**【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（78 pts）：$N \le 1000$，$E \le 5000$。 - Subtask 2（52 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le N,E \le 10^5$。 **【提示与说明】** 欢迎通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/omg15jba) 进行 hack。 **题目译自 [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_。** **本题分值按 COCI 原题设置，满分 $130$。**