#4344. [POI2016]Hydrorozgrywka

题目描述

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

输入格式

第一行包含两个正整数n,m(3<=n,m<=500000)，表示点数和边数。

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

输出格式

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

样例

样例输入

6 7  

1 2  

2 3  

3 1  

3 4  

4 5  

5 6  

6 3

样例输出

1  

1  

1  

2  

1  

2  

数据范围与提示