CF1811F Is It Flower?

Vlad 在自家院子里发现了一块长满了图的花坛，并决定带走其中一个。后来他发现，除了普通的图之外，花坛上还生长着 $k$-花。一个图被称为 $k$-花，如果它由一个长度为 $k$ 的简单环组成，并且通过该环的每一个顶点，都有一个属于自己的长度为 $k$ 的简单环，这些环在顶点上互不相交。例如，$3$-花如下图所示：  注意，$1$-花和 $2$-花不存在，因为形成一个环至少需要 $3$ 个顶点。 Vlad 非常喜欢 $k$-花的结构，现在他想知道自己带走的图是否恰好是某个 $k$-花。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。每个用例前有一个空行。 每个用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le \min(2 \cdot 10^5, \frac{n \cdot (n-1)}{2})$），分别表示图中的顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示一条连接顶点 $u$ 和 $v$ 的边。保证图中没有重边和自环。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，所有测试用例中 $m$ 的总和也不超过 $2 \cdot 10^5$。

输出 $t$ 行，每行对应一个测试用例的答案。如果 Vlad 的图是某个 $k$-花，输出 "YES"，否则输出 "NO"。 你可以以任意大小写输出答案（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定答案）。

由 ChatGPT 4.1 翻译