Problem Description

You are given a directed graph with $N$ nodes 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 two-player game.

Place two tokens on different nodes of the graph (you may use some cow-related items instead of tokens). Each turn, one player, Brain, chooses a token that must be moved along one outgoing edge. The other player, Hoof, chooses which outgoing edge to use to move that token. The two tokens are not allowed to be on the same node at any time. If at some point Hoof cannot make a legal move, then Brain wins. If the game can continue forever, then Hoof wins.

You are given $Q$ queries ($1 \leq Q \leq 10^5$), each containing the initial nodes of the two tokens. For each query, output which player wins.

Input Format

The first line contains $N$ and $M$.

The next $M$ lines each contain two integers $a$ and $b$, representing an edge from $a$ to $b$.

The graph contains no self-loops or multiple edges.

The next line contains $Q$.

The last $Q$ lines each contain two integers $x$ and $y$, satisfying $1\le x,y\le N$ and $x\neq y$, representing the initial nodes of the tokens.

Output Format

Output a string of length $Q$. The character B means Brain wins, and H means Hoof wins.

Note: the time limit for this problem is 4 seconds, which is twice the usual limit.

9 10
1 2
2 3
3 4
4 7
3 5
1 6
6 8
8 9
9 6
7 2
4
1 5
1 2
1 6
2 4

BHHB

Hint

Constraints

Brain can win the first game by choosing node $5$; then Hoof will have no legal move.

Brain can win the last game by choosing node $4$ and then choosing node $7$; then Hoof will have no legal move.

Hoof wins the other games.

Test Point Properties

• Test points 2-3 satisfy $N\le 100$, $M\le 200$.
• Test points 4-9 satisfy $N\le 5000$.
• Test points 10-21 have no additional constraints.

Translated by ChatGPT 5