分数: 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 无论执行什么操作,都没有有向循环的图。