← 返回题目列表

Codeforces · 1470/D

D. 奇怪的住房

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

冬季信息学院的学生将住在一组由地下通道连接的房屋中。老师们也会住在其中一些房子里,但不能随意住宿。出于安全原因,必须满足以下条件:

- 如果两栋房屋中都没有老师,则两栋房屋之间的所有通道都将被关闭。所有其他通道将保持开放。
- 应该可以使用开放的地下通道在任意两栋房屋之间移动。
- 教师不应居住在由通道直接连接的房屋中。

请主办方帮助选择教师居住的房屋,以满足安全要求或确定不可能。

输入

第一个输入行包含一个整数 $$$t$$$ — 测试用例的数量 ($$$1 \le t \le 10^5$$$)。

每个测试用例都以两个整数 $$$n$$$ 和 $$$m$$$ 开头 ($$$2 \le n \le 3 \cdot 10^5$$$, $$$0 \le m \le 3 \cdot 10^5$$$) - 房屋数量和通道数量。

接下来是 $$$m$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),描述房屋 $$$u$$$ 和 $$$v$$$ 之间的通道。确保没有两条通道连接同一对房屋。

所有测试用例的值 $$$n$$$ 的总和不超过 $$$3 \cdot 10^5$$$,并且所有测试用例的值 $$$m$$$ 的总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果无法选择所需的一组房屋,则输出“NO”。否则,输出“YES”,然后输出所选房屋的总数,然后以任意顺序输出所选房屋的索引。

示例

输入 #1

2
3 2
3 2
2 1
4 2
1 4
2 3

输出 #1

YES
2
1 3 
NO

输入 #2

1
17 27
1 8
2 9
3 10
4 11
5 12
6 13
7 14
8 9
8 14
8 15
9 10
9 15
10 11
10 15
10 17
11 12
11 17
12 13
12 16
12 17
13 14
13 16
14 16
14 15
15 16
15 17
16 17

输出 #2

YES
8
1 3 4 5 6 9 14 17

注意

下图显示了第二个示例测试。