Given a directed graph with \(N\) vertices and \(M\) edges (\(2 \leq N \leq 10^5\),
\(1 \leq M \leq 2 \cdot 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 \leq Q \leq 10^5\)) indicating the starting nodes
of the two tokens. For each query, output which player will win.

Problem credits: Danny Mittal

SCORING

• Test cases 2-3 satisfy \(N\le 100\), \(M\le 200\).
• Test cases 4-9 satisfy \(N\le 5000\).
• Test cases 10-21 satisfy no additional constraints.

Problem credits: Danny Mittal

The first line contains \(N\) and \(M\).

The next \(M\) lines each contain two integers \(a\) and \(b\), denoting an edge from
\(a\) to \(b\).

The graph does not contain self-loops or multiple edges.

The next line contains \(Q\).

The final \(Q\) lines each contain two integers \(x\) and \(y\) satisfying
\(1\le x,y\le N\) and \(x\neq y\), indicating the starting nodes of the tokens.

A string of length \(Q\), where each character is B for the brain winning and H
for the hoof winning.

*Note: the time limit for this problem is 4s, twice the default.*

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > US Open > Platinum