24284번 - Ludo 서브태스크다국어

A new game has appeared on the market - a version of the well-known game "Don't Angry Man!", named also "Ludo". Deni and Bob immediately decided to buy it and began to learn the rules: A map is given with fields numbered from 1 to N. Some pairs of fields are neighbor. There is a pawn that can be placed on a field and can be moved from a field to any neighboring field.

The map is special - starting from a field, the pawn cannot return to the same field without passing through previously visited fields. The first player chooses on which field to put the pawn. Then, it is a turn of the second player and the players begin to alternate moving the pawn from a field to some neighbor field. Every field that the pawn has visited becomes marked and the pawn can no longer step on it. The player who cannot move the pawn in a neighbor unmarked field loses and the other player wins. Deni and Bob have a lot of experience with similar games, so they will always play optimally. Deni starts the first move. She knows how to find a field, so that if she puts a pawn on it to start, she will win.

Write program ludo that reads the parameters of the game and for each field shows whether it is a winning position or not for the player making the first move.

From the first line of the standard input, your program reads two positive integers N and M - the count of fields on the map and the count of pairs of neighbors. From each of the following M lines, your program reads two integers x and y, which indicate that the fields numbered x and y are neighbor.

In order of fields' numbers, your program should output a sequence of 0 and 1 with no spaces, where 0 means that it is a losing position and 1 − if it is a winning posi2on for the first player.

• 1 ≤ N ≤ 5∙10⁵
• 1 ≤ M ≤ 5∙10⁵

The output means that for an optimal game, Deni loses if she places the pawn in the fields with numbers 1, 2 and 3, and in all the other fields she will win. If Deni places the pawn in the field with number 1, Bob can move the pawn in the field with number 3 and Deni will not have more moves because the field with number 1 is already marked. Analogously Deni will lose if she places the pawn in the field with number 2. For the fields with numbers 4 and 5, she has a winning strategy.