OpenJudge

1109:2013-07-12 染色

总时间限制:
20000ms
单个测试点时间限制:
1000ms
内存限制:
512000kB
描述

给定一个n个点m条边的无向图,要求给每条边2染色(即给每一条边赋值成1或者2),使得,对于任意一个度至少为2的点,与其相连的边中,既包含染色成1的边也包含染色成2的边。如果无解输出-1

输入
第一行包含两个正整数N和M,分别表示图中的边数和点数;
接下来M行,每行两个不同的在1到N之间的整数,描述一条边,输入数据中保证不存在重边。
输出
如果无解,输出一行一个整数-1。如果有解,则输出M行每行输出1或者2,第k个数字描述输入数据中的第k条边的颜色。
样例输入
5 6
1 2
2 3
3 1
3 4
1 4
4 5
样例输出
1
2
1
2
2
1
提示
对于100%的数据满足1≤N,M≤100000。
what is spj?

crf is sb
crf is sd
crf gg
crf zb
crf hsg
crf 刷霸
有问题找zhx

全局题号
6089
添加于
2013-07-12
提交次数
2
尝试人数
1
通过人数
0