페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5722

Hoof and Brain 4초 256MB

문제

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.


입력

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≤x,y≤N and x≠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.


예제1

입력
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

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.



출처

USACO 2022 US Open Platinum

역링크 공식 문제집만