A6119. 「USACO 2022 US Open Platinum」Hoof and Brain
编程题
省选/NOI-
知识点
题目描述
**题目来自 [USACO 2022 US Open Contest, Platinum](http://usaco.org/index.php?page=open22results) Problem 2. [Hoof and Brain](http://usaco.org/index.php?page=viewproblem2&cpid=1237)**
给定一个包含 $N$ 个结点和 $M$ 条边的有向图（$2 \leq N \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$），Farmer John 的奶牛们喜欢玩以下的双人游戏。
在图中的不同结点上放置两个指示物（可以用一些与奶牛相关的物品代替指示物）。每一回合，一名玩家，脑，选择一个需要沿某一条出边移动的指示物。另一名玩家，蹄，选择沿着哪条出边移动该指示物。两个指示物在任何时刻不允许处于同一个结点上。如果在某些时刻蹄不能做出合法的行动，则脑获胜。如果游戏可以无限进行下去，则蹄获胜。
给定 $Q$ 个询问（$1 \leq Q \leq 10^5$），包含两个指示物所在的初始结点。对于每个询问，输出哪名玩家获胜。
给定一个包含 $N$ 个结点和 $M$ 条边的有向图（$2 \leq N \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$），Farmer John 的奶牛们喜欢玩以下的双人游戏。
在图中的不同结点上放置两个指示物（可以用一些与奶牛相关的物品代替指示物）。每一回合，一名玩家，脑，选择一个需要沿某一条出边移动的指示物。另一名玩家，蹄，选择沿着哪条出边移动该指示物。两个指示物在任何时刻不允许处于同一个结点上。如果在某些时刻蹄不能做出合法的行动，则脑获胜。如果游戏可以无限进行下去，则蹄获胜。
给定 $Q$ 个询问（$1 \leq Q \leq 10^5$），包含两个指示物所在的初始结点。对于每个询问，输出哪名玩家获胜。
输入格式
输入的第一行包含 $N$ 和 $M$。
以下 $M$ 行每行包含两个整数 $a$ 和 $b$，表示一条从 $a$ 连向 $b$ 的边。
图中不包含自环或重边。
下一行包含 $Q$。
最后 $Q$ 行每行包含两个整数 $x$ 和 $y$，满足 $1\le x,y\le N$ 以及 $x\neq y$，表示指示物所在的初始结点。
以下 $M$ 行每行包含两个整数 $a$ 和 $b$，表示一条从 $a$ 连向 $b$ 的边。
图中不包含自环或重边。
下一行包含 $Q$。
最后 $Q$ 行每行包含两个整数 $x$ 和 $y$，满足 $1\le x,y\le N$ 以及 $x\neq y$，表示指示物所在的初始结点。
输出格式
输出一个长为 $Q$ 的字符串，其中字符
B 表示脑获胜，H 表示蹄获胜。输入输出样例
输入 #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
输出 #1
BHHB
说明/提示
测试点 $2\sim 3$ 满足 $N\le 100$，$M\le 200$。
测试点 $4\sim 9$ 满足 $N\le 5000$。
测试点 $10\sim 21$ 没有额外限制。
测试点 $4\sim 9$ 满足 $N\le 5000$。
测试点 $10\sim 21$ 没有额外限制。