题目描述

存在一个包含 $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" 均视为有效输出。

样例

1
7 8 10
1 2
1 3
1 4
2 5
3 6
5 7
2 3
3 4
2 1
1 3
1 4
2 1
2 2
2 3
2 4
2 5
2 6
2 7

YES
NO
YES
NO
NO
YES
YES
YES

样例说明

下方为样例中的图：

• 初始时所有节点均为蓝色。因此 Cry 不会失败，最终令牌一定会被移至一个无出边的节点。
• 将节点 3 和 4 涂为红色后，在采用最优策略的情况下：从节点 1、3、4 开始游戏时，River 会获胜。若游戏从节点 1 开始，一种可能的进程如下：
  1. Cry 将令牌移至节点 2。
  2. River 将令牌移至节点 3（该节点为红色），因此 River 获胜。

可以证明，对于其他所有节点，采用最优策略时 Cry 仍会获胜。

来源

Codeforces 2137G，英文题名 Cry Me a River。