← 返回题目列表

Codeforces · 2137/G

G. 哭我一条河

中文机器翻译题面 查看原题

有一个有向无环图,其中有 $$$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。每个字母可以以大写或小写形式输出。

示例

输入
复制

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 的胜利。如果游戏从节点 $$$3$$$ 和 $$$4$$$ 开始,则 River 立即获胜。如果游戏从节点 $$$1$$$ 开始,游戏可以进行的一种方式如下:

  • Cry 将代币移动到节点 $$$2$$$。
  • River 将代币移动到节点 $$$3$$$,该节点是红色的,因此 River 获胜。
.

可以证明,Cry 仍然以所有其他节点的最佳发挥获胜。