【问题描述】

给定一个包含 N 个结点和 M 条边的有向图（2≤N≤10^5, 1≤M≤2⋅10^5），Farmer John 的奶牛们喜欢玩以下的双人游戏。

在图中的不同结点上放置两个指示物（可以用一些与奶牛相关的物品代替指示物）。每一回合，一名玩家，脑，选择一个需要沿某一条出边移动的指示物。另一名玩家，蹄，选择沿着哪条出边移动该指示物。两个指示物在任何时刻不允许处于同一个结点上。如果在某些时刻蹄不能做出合法的行动，则脑获胜。如果游戏可以无限进行下去，则蹄获胜。

给定 Q 个询问（1≤Q≤10^5），包含两个指示物所在的初始结点。对于每个询问，输出哪名玩家获胜。

【输入格式】

输入的第一行包含 N 和 M。

以下 M 行每行包含两个整数 a 和 b，表示一条从 a 连向 b 的边。

图中不包含自环或重边。

下一行包含 Q。

最后 Q 行每行包含两个整数 x 和 y，满足 1≤x,y≤N 以及 x≠y，表示指示物所在的初始结点。

【输出格式】

输出一个长为 Q 的字符串，其中字符 B 表示脑获胜，H 表示蹄获胜。

注意：本题的时间限制为 4 秒，通常限制的两倍。

【输入样例】

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

脑可以通过选择结点 5 赢得第一局游戏；此时蹄将没有合法的行动。

脑可以通过选择结点 4 然后选择结点 7 赢得最后一局游戏；此时蹄没有合法的行动。

蹄赢得其他局游戏。

【测试点性质】

测试点 2-3 满足 N≤100，M≤200。

测试点 4-9 满足 N≤5000。

测试点 10-21 没有额外限制。

供题：Danny Mittal