AT_agc077_c [AGC077C] Reverse and DAG

给定一个有 $N$ 个顶点、$M$ 条边的简单有向图 $G$，顶点编号为 $1$ 到 $N$，第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$。保证对于任意 $i \neq j$，都有 $(a_i,b_i) \neq (b_j,a_j)$。另外，给定一个整数 $K$，其中 $2 \leq K \leq N-2$。 你可以进行如下操作任意次（也可以不进行）： - 选择一个大小为 $K$ 的顶点子集 $S \subset \{1,\ldots,N\}$。对于所有两端点编号都在 $S$ 中的有向边，反转该边的方向。 - 即，若存在一条从 $u$ 到 $v$ 的边（$u,v \in S$），将其删除，同时加入一条从 $v$ 到 $u$ 的有向边。所有符合条件的边会同时进行此操作。 问是否可以通过若干次这样的操作（包括零次），将 $G$ 变成一个没有有向环的图（DAG）。 共给出 $T$ 组测试数据，请分别作答。

输入按如下格式从标准输入读入： > $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$

请按顺序输出第 $1$、$2$、…、$T$ 个测试数据的答案。 对于每组测试数据，若可以通过若干次操作使 $G$ 变为无环有向图，输出 `Yes`，否则输出 `No`。

### 样例解释 1 对于第一组数据，可以通过如下两步操作使 $G$ 变为无环图： - 第一步，选择 $S = \{1,2,7\}$，此时两端都属于 $S$ 的有向边为 $1 \to 2$ 和 $7 \to 1$，这两条边方向被反转。 - 第二步，选择 $S = \{4,5,7\}$，此时 $4 \to 5$ 是唯一一条两端在 $S$ 的有向边，方向反转，$G$ 变为无环有向图。 对于第二组数据，无论如何操作，都无法将 $G$ 变为无环有向图。 ### 数据范围 - $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$ - $i \neq j$ 时，$(a_i, b_i) \neq (a_j, b_j)$ 且 $(a_i, b_i) \neq (b_j, a_j)$。 - 所有测试数据中 $N$ 的总和不超过 $2\times 10^5$。 - 所有测试数据中 $M$ 的总和不超过 $2\times 10^5$。 - 所有输入均为整数。 由 ChatGPT 5 翻译