Hoof and Brain

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, chooses a token that must be moved along an outgoing edge. The other player, the hoof, chooses which edge the token moves along. The two tokens can never be on the same node. If at some point the hoof cannot 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$) giving the starting nodes of the two tokens. For each query, output which player wins.

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 has no 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$, giving the starting nodes of the tokens.

Output a string of length $Q$. Each character is B if the brain wins and H if the hoof wins.

The brain can win the first game by selecting node 5. Then the hoof has no valid move.

The brain can win the last game by selecting node 4 and then node 7. Then the hoof has no valid move.

The hoof wins the other games.