403394: GYM101149 I It's the Police
Description
Yuriy is a corrupted head of police. Every day he has to set policemen to the posts in the city so that local gangs still could commit crimes. The city has n squares connected by m streets so that the j-th street connects the aj-th and the bj-th squares. A policeman, being set on some square, can observe this square and also all squares connected with it. Yuriy wants to set policemen in such a way that at least one square is not observed, which lets the gangs to do their dark business on this square. Of course, Yuriy doesn't want to be suspicious, so he plans to set policemen to as many squares as possible.
InputThe first line contains two space-separated integers: n and m (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105) — the numbers of squares and streets in the city.
Each of the next m lines contains two space-separated integers: aj and bj (1 ≤ aj, bj ≤ n, aj ≠ bj) — the numbers of squares connected by the j-th street. Every pair of squares can be connected by at most one street.
OutputOutput n space-separated integers. On the i-th position output 1, if a policeman should be set to the i-th square, or 0 if it shouldn't be done. If there are many possible solutions, output any of them.
ExamplesInput5 5Output
1 2
2 3
3 4
4 5
5 1
0 0 1 1 0Input
6 4Output
1 2
3 4
3 5
3 6
0 0 1 1 1 1