Ludo
Time limit2sMemory limit1024 MB
On a graph where no vertex repeats on any path, decide for each starting vertex whether the first player wins the game of moving a pawn to unvisited neighbors.
- Level
Medium7 of 10
- Topics
- Graph, DFS, Game theory, Tree
- Solved
- No attempts yet
Problem
A new game has appeared on the market: a version of the well-known game "Don't Angry Man!", also called "Ludo". Deni and Bob immediately bought it and began to learn the rules. A map is given with fields numbered from 1 to N. Some pairs of fields are neighbors. 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 the second player's turn, and the players alternate moving the pawn from a field to some neighboring 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 to a neighboring unmarked field loses, and the other player wins. Deni and Bob have a lot of experience with similar games, so they always play optimally. Deni makes the first move. She knows how to find a field such that if she puts the pawn on it to start, she will win.
Write a program ludo that reads the parameters of the game and, for each field, reports whether it is a winning position or not for the player making the first move.
Input
From the first line of the standard input, your program reads two positive integers N and M: the number of fields on the map and the number 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 neighbors.
Output
In order of field numbers, your program should output a sequence of 0 and 1 with no spaces, where 0 means a losing position and 1 means a winning position for the first player.
Constraints
- 1 ≤ N ≤ 5∙10^5
- 1 ≤ M ≤ 5∙10^5
Hint
The output means that in an optimal game Deni loses if she places the pawn in the fields numbered 1, 2, and 3, and she wins in all the other fields. If Deni places the pawn in the field numbered 1, Bob can move the pawn to the field numbered 3, and Deni will have no more moves because the field numbered 1 is already marked. Deni likewise loses if she places the pawn in the field numbered 2. For the fields numbered 4 and 5, she has a winning strategy.