CF1817B Fish Graph

给定一个包含 $n$ 个节点和 $m$ 条边的简单无向图。注意，该图不一定是连通的。节点编号为 $1$ 到 $n$。 我们定义“Fish Graph”为：图中存在一个简单环，且环上有一个特殊节点 $u$。除了环上的边外，图中还应恰好有 $2$ 条额外的边，这两条边都与节点 $u$ 相连，但不能与环上的其他节点相连。 请判断该图中是否存在一个子图是 Fish Graph。如果存在，请输出任意一个这样的子图。 在本题中，子图指的是从原图中选取任意一些边得到的图。  示例 1 的可视化。红色的边构成了一个可能的 Fish Graph 子图。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2000$），分别表示节点数和边数。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$），表示一条连接 $u_i$ 和 $v_i$ 的边。 保证没有两条边连接同一对无序节点。 另外，保证所有测试用例中 $n$ 的总和和 $m$ 的总和都不超过 $2000$。

对于每个测试用例，如果图中存在一个子图是 Fish Graph，输出 "YES"，否则输出 "NO"。如果答案为 "YES"，在接下来的若干行输出该子图的描述。 描述的第一行包含一个整数 $k$，表示该子图的边数。 接下来的 $k$ 行，每行输出两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示子图中的一条边。$u$ 和 $v$ 的顺序无关紧要，只要原图中存在这条边即可。输出边的顺序也无关紧要，只要结果构成一个 Fish Graph 即可。 如果有多组解，输出任意一组均可。

在第一个示例中，一个合法的子图包含环 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1$。该环的特殊节点为 $4$。两条额外的边 $4-5$ 和 $4-6$ 都与 $4$ 相连，构成了 Fish Graph。 在第二个示例中，一个合法的子图包含环 $1 \rightarrow 3 \rightarrow 4 \rightarrow 1$。该环的特殊节点为 $3$。两条额外的边 $3-2$ 和 $3-5$ 都与 $3$ 相连，构成了 Fish Graph。 在最后一个示例中，可以证明不存在合法的子图。 由 ChatGPT 4.1 翻译