CF2137G Cry Me a River
题目描述
存在一个包含 $n$ 个节点和 $m$ 条边的**有向无环图**。所有节点初始时均为蓝色。
定义“趣味图游戏”（fun graph game）规则如下：
1. 初始时，将一枚令牌放置在节点 $s$ 上。
2. Cry 和 River 轮流将令牌移动到一个满足“存在从当前节点指向该节点的有向边”的节点上，其中 **Cry 先手**。
3. 若令牌在**任一玩家的回合后**到达一个无出边的节点，则 Cry 获胜。
4. 若令牌在**任一玩家的回合后**到达一个红色节点，则 River 获胜。
5. **特殊规则**：若玩家到达一个“既为红色又无出边”的节点，则 River 获胜。
由于该图是有向无环图，可证明游戏一定会在有限回合内结束。
需注意：若起始节点 $s$ 无出边，则 Cry 可立即获胜；若起始节点 $s$ 为红色，则 River 可立即获胜。
你需要处理 $q$ 个如下类型的查询：
- 1 u：将节点 $u$ 的颜色更新为红色。保证执行此更新前，节点 $u$ 为蓝色。
- 2 u：若令牌初始放置在节点 $u$ 上进行“趣味图游戏”，且两名玩家均采用最优策略，Cry 会获胜吗？
输入格式
每组测试包含多组测试用例。第一行输入测试用例的数量 $t$（$1 \leq t \leq 10^4$），随后依次描述每组测试用例。
每组测试用例的输入格式如下：
1. 第一行：三个整数 $n$、$m$、$q$（$2 \leq n \leq 2 \times 10^5$，$1 \leq m,q \leq 2 \times 10^5$）。
2. 接下来 $m$ 行：每行包含两个整数 $u$ 和 $v$（$1 \leq u,v \leq n$），表示存在一条从 $u$ 指向 $v$ 的有向边。
3. 接下来 $q$ 行：每行包含两个整数 $x$ 和 $u$（$1 \leq x \leq 2$，$1 \leq u \leq n$），分别表示查询类型和查询所针对的节点。
保证给定的图是有向无环图，且不会重复给出同一条边。同时保证所有测试用例的 $n$ 之和、$m$ 之和、$q$ 之和均不超过 $2 \times 10^5$。
输出格式
对于每个类型 2 的查询，若 Cry 获胜则输出 "YES"，否则输出 "NO"。字母不区分大小写，例如 "Yes" 、 "no" 均视为有效输出。
说明/提示
下方为样例中的图：
- 初始时所有节点均为蓝色。因此 Cry 不会失败，最终令牌一定会被移至一个无出边的节点。
- 将节点 3 和 4 涂为红色后，在采用最优策略的情况下：从节点 1、3、4 开始游戏时，River 会获胜。若游戏从节点 1 开始，一种可能的进程如下：
1. Cry 将令牌移至节点 2。
2. River 将令牌移至节点 3（该节点为红色），因此 River 获胜。
可以证明，对于其他所有节点，采用最优策略时 Cry 仍会获胜。