Given a directed graph with N vertices and M edges (2≤N≤10^5, 1≤M≤2⋅10^5), Farmer John's cows like to play the following game with two players.

Place two tokens on distinct nodes in the graph. Each turn, one player, the brain, will choose a token that must be moved along an outgoing edge. The other player, the hoof, will choose which edge to move the token along. The two tokens can never be on the same node. If at some point the hoof can't make a valid move, the brain wins. If the game continues indefinitely, the hoof wins.

You are given Q queries (1≤Q≤10^5) indicating the starting nodes of the two tokens. For each query, output which player will win.

#5722 upload - done - how_to_reg -

Hoof and Brain timer 4s memory 256MB

#5722

Hoof and Brain 4s 256MB