Hoof and Brain

题目描述

给定一张有向图，包含 $N$ 个点和 $M$ 条边（$2 \leq N \leq 10^5$， $1 \leq M \leq 2 \cdot 10^5$），Farmer John 的奶牛喜欢进行如下的双人游戏。 在图中两个不同的点上放置两个棋子。每一回合，一名玩家（brain）将选择一个棋子，该棋子必须沿着一条出边移动。另一名玩家（hoof）将选择具体沿哪一条边移动该棋子。两个棋子永远不能在同一个点上。如果在某个时刻 hoof 无法进行合法移动，则 brain 获胜。如果游戏可以无限进行下去，则 hoof 获胜。 给定 $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$，表示两个棋子的起始点。

输出格式

输出一个长度为 $Q$ 的字符串，其中每个字符若为 B 表示 brain 获胜，若为 H 表示 hoof 获胜。 注意：本题时限为 4s，为默认时限的两倍。

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

提示

brain 可以通过选择点 5 来赢下第一局；此时 hoof 没有合法移动。 brain 可以通过先选择点 4 再选择点 7 来赢下最后一局；此时 hoof 没有合法移动。 其余对局由 hoof 获胜。 SCORING: 测试点 2-3 满足 $N\le 100$，$M\le 200$。 测试点 4-9 满足 $N\le 5000$。 测试点 10-21 无额外限制。 题目来源：Danny Mittal

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum