|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||21||14||14||77.778%|
To determine their social position, spies like to play games of wit and cunning. One of these games is the dreaded alternating game. It is played by two players, who are called player even and player odd. These strange player names are used to determine the winner of each game: player even wins if the number of moves in the completed game was even, and similarly player odd wins if the number of moves was odd.
Every game is played on a specially prepared game board, consisting of places and one-way connections between certain pairs of places. Every place is controlled by one of the two players. The game starts by putting a token on the starting place of the game board. Every turn, the player who controls the place where the token resides must make a move by moving the token along one of the outgoing connections of that place. This continues until no more move is possible, at which point the winner of the game is known. All game boards are constructed such that inﬁnite games are impossible.
The rules of the game state that both spies playing the game must come to an agreement on which player each one will be. The spies have ﬁgured out that picking their player is the most important part of the game. Special agent Walker wants to win every game she plays to improve her social position. She can play the game perfectly if she knows which player to pick at the start of the game. She developed a special set of skills to ensure that she will always get to be the player she wants to be. It is your task to help her pick the best player for a speciﬁc game board. Better make sure it is correct; you do not want to disappoint special agent Walker.
A visual representation of the third sample. The dark circles indicate places controlled by the even player. Despite having the ﬁrst move, the odd player loses. If he moves the token from 1 to 3, the even player wins directly by moving the token to 4. If the odd player moves the token to 2, the even player ﬁrst moves the token to 3 (as he must) and then to 5, after which the odd player is forced to move the token to 6 and thus loses (four moves were made). Similarly, moving the token to 5 at the ﬁrst move leads to an automatic win for the even player.
On the ﬁrst line one positive number: the number of test cases, at most 100. After that per test case:
Per test case:
3 2 1 1 0 1 1 2 6 6 1 1 0 1 1 1 0 1 2 2 3 2 5 3 4 4 6 5 6 6 7 1 1 0 0 1 1 0 1 2 1 3 1 5 2 3 3 4 3 5 5 6
1 0 0