← 返回题目列表

AtCoder · agc077_c

C. 反向和 DAG

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

分数: 1000 点

问题陈述

有一个简单的有向图 G 与 N 顶点和 M 边缘。顶点已编号 1 通过 N,以及 i- 第一条边从顶点出发 a_i 到顶点 b_i。可以保证 (a_i,b_i)\neq (b_j,a_j) 为 i\neq j。另外,一个整数 给出了 K 与 2 \leq K \leq N-2 。

判断是否可以使 G 通过执行以下操作零次或多次来获得没有有向循环 (DAG) 的图。

  • 选择尺寸-K 子集 S of \lbrace 1,\ldots,N\rbrace。对于每条有向边,其两个端点的编号都在 S,反转其方向。
    • 也就是说,如果有一条来自顶点的边 u 到顶点 v\ (u,v\in S),删除该边并从顶点添加有向边 v 到顶点 u。对于所有适用的边缘同时执行此操作。

T 给出了测试用例;解决它们中的每一个。 每个输入中的

约束

  • 1 \leq T \leq 50000
  • 4 \leq N \leq 2\times 10^5
  • 0 \leq M \leq \min({N(N-1), 2\times 10^5})
  • 2 \leq K \leq N-2
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i
  • (a_i, b_i) \neq (a_j, b_j) 和 (a_i,b_i) \neq (b_j,a_j) 为 i\neq j.
  • 总和 N 最多为 2\times 10^5.
  • 总和 M 最多为 2\times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N M K
a_1 b_1
a_2 b_2
\vdots
a_M b_M

输出

输出以下问题的答案 \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T 按以下格式顺序排列。

输出 Yes 如果可以的话 G 通过执行零次或多次操作,得到一个没有有向循环 (DAG) 的图,以及 通过执行以下两个操作,可以将 No 否则。


示例输入 1

3
7 10 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6
7 1
7 19 5
1 4
2 3
2 4
2 5
3 5
3 6
3 7
4 3
4 6
4 7
5 1
5 4
5 6
6 1
6 2
6 7
7 1
7 2
7 5
9 15 5
1 6
2 7
2 9
3 1
3 4
4 5
4 6
4 7
4 8
5 7
5 9
6 5
6 9
7 9
8 9

示例输出 1

Yes
No
Yes

在第一个测试用例中, G 制作成无向循环图。

  • 在第一个操作中,执行操作 S = \lbrace 1, 2,7 \rbrace。两个端点编号都在的有向边 S 是来自顶点的边 1 到顶点 2 和顶点的边 7 到顶点 1。这些边缘的方向相反。

  • 在第二个操作中,执行操作 S = \lbrace 4, 5,7 \rbrace。两个端点编号都在的有向边 S 是来自顶点的边 4 到顶点 5。该边缘的方向相反,并且 G 变成没有有向循环的图。

在第二个测试用例中,不可能使 G 无论执行什么操作,都没有有向循环的图。