题目描述

给定一张含 $N$ 个结点、$E$ 条边的无向图。

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

输入格式

第一行，两个整数 $N,E$。

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

输出格式

若无解，请输出 $0$。

否则输出 $E$ 行，每行输出一条边所染成的颜色（与输入顺序对应）。红色用 $1$ 表示，蓝色用 $2$ 表示。

如果存在多解，请输出任意一种。

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

提示

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（78 pts）：$N \le 1000$，$E \le 5000$。
• Subtask 2（52 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,E \le 10^5$。

【提示与说明】

欢迎通过私信或发帖对自行编写的 Special Judge 进行 hack。

题目译自 COCI 2009-2010 CONTEST #7 Task 6 RESTORAN。

本题分值按 COCI 原题设置，满分 $130$。