Given a directed graph with NN vertices and MM edges (2≤N≤1052≤N≤105, 1≤M≤2⋅1051≤M≤2⋅105), Farmer John's cows like to play the following game with two pla
Place two tokens on distinct nodes in the graph. Each turn, one pla
You are given QQ queries (1≤Q≤1051≤Q≤105) indicating the starting nodes of the two tokens. For each query, output which pla
**Note: the time limit for this problem is 4s, twice the default.**
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.
Problem credits: Danny Mittal
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains NN and MM.
The next MM lines each contain two integers aa and bb, denoting an edge from aa to bb.
The graph does not contain self-loops or multiple edges.
The next line contains QQ.
The final QQ lines each contain two integers xx and yy satisfying 1≤x,y≤N1≤x,y≤N and x≠yx≠y, indicating the starting nodes of the tokens.
OUTPUT FORMAT (print output to the terminal / stdout):
A string of length QQ, where each character is B for the brain winning and H for the hoof winning.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
BHHB
SCORING: