F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 4344. -- [POI2016]Hydrorozgrywka

4344: [POI2016]Hydrorozgrywka

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 68  Solved: 8
[Submit][Status][Discuss]

Description

给定一个n个点m条边的无向连通图,保证每条边最多属于一个环。两个人在这张图上玩游戏,一开始他们会在某个节点放一个棋子,然后依次移动这个棋子,已经走过的边不能再走,谁不能移动谁就输了。请求出所有先手必胜的游戏开始时放棋子的位置。

Input

第一行包含两个正整数n,m(3<=n,m<=500000),表示点数和边数。
接下来m行每行包含两个正整数a,b(1<=a,b<=n,a!=b),表示a点到b点之间有一条无向边。

Output

包含n行,对于第i行,如果在i点放棋子先手必胜,输出1,否则输出2。

Sample Input

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

Sample Output

1
1
1
2
1
2

HINT

Source

鸣谢Claris

[Submit][Status][Discuss]

HOME Back