给您一个简单的无向图,其中包含 $$$n$$$ 节点和 $$$m$$$ 边。请注意,该图不一定是连通的。节点的标记范围为 $$$1$$$ 到 $$$n$$$。
如果一个图包含一个简单的循环,并且有一个属于该循环的特殊节点 $$$u$$$,那么我们将它定义为鱼图。除了循环中的边之外,图表还应该有 $$$2$$$ 额外的边。两条边都应连接到节点 $$$u$$$,但它们不应连接到循环的任何其他节点。
确定该图是否包含鱼图的子图,如果是,则找到任何此类子图。
在这个问题中,我们将子图定义为通过获取原始图的边的任意子集而获得的图。
示例 1 的可视化。红色边缘形成一个可能的子图,即鱼图。
输入
输入的第一行包含整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$),即测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数,$$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2\,000$$$) - 节点数和边数。
接下来的 $$$m$$$ 行中的每一行都包含一条边的描述。每行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i\neq v_i$$$) - 一条边将节点 $$$u_i$$$ 连接到节点 $$$v_i$$$。
保证没有两条边连接同一对无序节点。
此外,保证所有测试用例的$$$n$$$总和和$$$m$$$总和不超过$$$2\,000$$$。
输出
对于每个测试用例,如果图形包含鱼图的子图,则输出“YES”,否则输出“NO”。如果答案为“是”,则在以下行中输出子图的描述。
描述的第一行包含一个整数 $$$k$$$ — 子图的边数。
在接下来的 $$$k$$$ 行中,输出所选子图的边。每条 $$$k$$$ 行都应包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u, v\le n$$$, $$$u\neq v$$$) - $$$u$$$ 和 $$$v$$$ 之间的边属于子图。 $$$u$$$ 和 $$$v$$$ 的打印顺序并不重要,只要这两个节点通过原始图中的边连接即可。只要生成的子图是鱼图,打印边缘的顺序并不重要。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
3 7 8 1 2 2 3 3 4 4 1 4 5 4 6 4 2 6 7 7 7 6 7 1 2 2 3 3 4 4 1 1 3 3 5 4 4 1 3 3 4 4 1 1 2
输出 #1
YES 6 5 4 6 4 4 3 1 4 2 1 3 2 YES 5 5 3 2 3 3 1 4 3 1 4 NO
注意
在第一个示例中,可能的有效子图包含循环 $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1$$$。本次循环的特殊节点是节点$$$4$$$。两条额外的边 $$$4 - 5$$$ 和 $$$4 - 6$$$ 都连接到 $$$4$$$,完成鱼图。
在第二个示例中,可能的有效子图包含循环 $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 1$$$。本次循环的特殊节点是节点$$$3$$$。两条额外的边 $$$3 - 2$$$ 和 $$$3 - 5$$$ 都连接到 $$$3$$$,完成鱼图。
在最后一个例子中,可以证明不存在有效的子图。