← 返回题目列表

Codeforces · 1239/F

F. 刷卡,不刷卡!

中文机器翻译题面 查看原题

在期待新的冒险时,布茨想做一件好事。与地图和背包讨论后,他们决定送给朵拉一张连通图。经过长时间的搜索,Boots 选择了 $$$t$$$ 图的变体,Dora 可能会喜欢。然而狐狸斯威珀却想破坏他的计划。

Swiper 知道,Dora 现在只能数到 $$$3$$$,所以他提出了以下想法。他想窃取一些非空的顶点集,这样朵拉就不会注意到丢失的情况。他决定窃取一些非空顶点集,以便在删除被窃取的顶点和与其相邻的边后,每个剩余的顶点都不会改变其模 $$$3$$$ 的度数。顶点的度数是与其相邻的边的数量。窃取所有顶点会很可疑,因此 Swiper 需要另一个计划。

靴子确信,这种犯罪是不能允许的。然而,他们担心,他们无法独自解决这个问题。因此布茨决定寻求你的帮助。请针对每个图表的变体确定 Swiper 是否可以执行盗窃。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100\,000$$$) — 图形变体的数量。

每个变体的第一行包含整数 $$$n$$$, $$$m$$$ ($$$1 \le n \le 500\,000$$$, $$$0 \le m \le 500\,000$$$),图中顶点和边的数量。

接下来是 $$$m$$$ 行,每行包含整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$),即与相应边连接的顶点的索引。

保证图是连通的并且不包含多条边或自环。

保证所有变体的 $$$n$$$ 总和最多为 $$$500\,000$$$,所有变体的 $$$m$$$ 总和最多为 $$$500\,000$$$。

图表变体的描述用空行分隔。

输出

对于每个变体:

- 如果答案存在,则打印“Yes”,然后打印答案本身。第一行应包含一个整数 $$$c$$$ ($$$1 < c < n$$$),即骗子可以窃取的顶点数量,而 Dora 不会注意到丢失。在下一行打印 $$$c$$$ 不同的整数,即任意顺序的图顶点的索引。
- 否则打印“否”。

如果有多种正确的方法来窃取顶点,请打印其中任何一个。

请注意,不需要最大化被盗顶点的数量。

示例

输入 #1

3
3 3
1 2
2 3
3 1

6 6
1 2
1 3
2 3
2 5
2 6
2 4

8 12
1 2
1 3
2 3
1 4
4 5
5 1
3 6
3 7
3 8
6 1
7 1
8 1

输出 #1

No
Yes
3
4 5 6
Yes
3
6 7 8

注意

下图显示了示例测试中的第三个变体。骗子可以窃取的顶点集用粗体表示。