U219682 [USACO 2022 US Open Contest, P, P2] 蹄和脑

给定一个包含 $N$ 个结点和 $M$ 条边的有向图，Farmer John 的奶牛们喜欢玩以下的双人游戏。 在图中的不同结点上放置两个指示物（可以用一些与奶牛相关的物品代替指示物）。每一回合，一名玩家，脑，选择一个需要沿某一条出边移动的指示物。另一名玩家，蹄，选择沿着哪条出边移动该指示物。两个指示物在任何时刻不允许处于同一个结点上。如果在某些时刻蹄不能做出合法的行动，则脑获胜。如果游戏可以无限进行下去，则蹄获胜。 给定 $Q$ 个询问，包含两个指示物所在的初始结点。对于每个询问，输出哪名玩家获胜。

输入的第一行包含 $N$ 和 $M$。 以下 $M$ 行每行包含两个整数 $a$ 和 $b$，表示一条从 $a$ 连向 $b$ 的边。 图中不包含自环或重边。 下一行包含 $Q$。 最后 $Q$ 行每行包含两个整数 $x$ 和 $y$，表示指示物所在的初始结点。

输出一个长为 $Q$ 的字符串，其中字符 `B` 表示脑获胜，`H` 表示蹄获胜。 **注意：本题的时间限制为 4 秒，通常限制的两倍。**

【数据范围】 - $2\le N\le10^5$。 - $1\le M\le2\times10^5$。 - $1\le Q\le105$。 - $1\le x$。 - $y\le N$。 - $x\ne y$。 【测试点性质】 - 测试点 2-3 满足 $N\le100$，$M\le200$。 - 测试点 4-9 满足 $N\le5000$。 - 测试点 10-21 没有额外限制。 【样例说明】 #### 样例组 #1 脑可以通过选择结点 5 赢得第一局游戏；此时蹄将没有合法的行动。 脑可以通过选择结点 4 然后选择结点 7 赢得最后一局游戏；此时蹄没有合法的行动。 蹄赢得其他局游戏。