有一个有向无环图,其中有 $$$n$$$ 个节点和 $$$m$$$ 边。每个节点最初都是蓝色的。
让我们定义 有趣的图形游戏 如下:
- 最初,一个令牌被放置在节点 $$$s$$$ 上。
- Cry 和 River 轮流将令牌移动到一个节点,以便存在从其当前位置到该节点的有向边,Cry 首先移动。
- 如果令牌在任一玩家回合后到达没有传出边的节点,则 Cry 获胜。
- 如果令牌在任一玩家回合后到达红色节点,则河牌获胜。
- 如果玩家到达一个既是红色又没有传出边的节点,则河牌获胜。
由于该图是非循环的,因此可以证明游戏总是以有限的回合数结束。
请注意,如果起始节点 $$$s$$$ 没有出边,或者分别为红色,则 Cry 和 River 可以立即赢得比赛。
您必须处理以下类型的 $$$q$$$ 查询:
- 1 u:将节点 $$$u$$$ 的颜色更新为红色。保证节点 $$$u$$$ 在这次更新之前是蓝色的。
- 2 u:如果 有趣的图形游戏 最初在节点 $$$u$$$ 处使用代币进行游戏,并且两个玩家都发挥最佳状态,Cry 会赢吗?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$、$$$q$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$ 、$$$1 \leq m,q \leq 2\cdot 10^5$$$)。
下面的 $$$m$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n$$$),这意味着从 $$$u$$$ 到 $$$v$$$ 有一条边。
以下 $$$q$$$ 行每行包含两个整数 $$$x$$$ 和 $$$u$$$ ($$$1 \leq x \leq 2, 1 \leq u \leq n$$$) – 表示查询类型和执行查询的节点。
保证给定的图是有向无环图。此外,不会多次给予优势。
保证所有测试用例中 $$$n$$$ 的总和、$$$m$$$ 的总和以及 $$$q$$$ 的总和不超过 $$$2\cdot 10^5$$$。
输出
对于第二类型的每个查询,输出 是 如果Cry获胜。否则,输出 NO。每个字母可以以大写或小写形式输出。
示例
输入复制
17 8 101 21 31 42 53 65 72 33 42 11 31 42 12 22 32 42 52 62 7
输出复制
YES NO YES NO NO YES YES YES
注意
下面显示了示例中的图表。
最初,所有节点都是蓝色的。因此,Cry 不会丢失,最终令牌将被移动到没有传出边缘的节点。
在节点 $$$3$$$ 和 $$$4$$$ 被涂成红色后,节点 $$$1,3,4$$$ 现在在最佳状态下开始作为 River 的胜利。如果游戏从节点 $$$3$$$ 和 $$$4$$$ 开始,则 River 立即获胜。如果游戏从节点 $$$1$$$ 开始,游戏可以进行的一种方式如下:
- Cry 将代币移动到节点 $$$2$$$。
- River 将代币移动到节点 $$$3$$$,该节点是红色的,因此 River 获胜。
可以证明,Cry 仍然以所有其他节点的最佳发挥获胜。