冬季信息学院的学生将住在一组由地下通道连接的房屋中。老师们也会住在其中一些房子里,但不能随意住宿。出于安全原因,必须满足以下条件:
- 如果两栋房屋中都没有老师,则两栋房屋之间的所有通道都将被关闭。所有其他通道将保持开放。
- 应该可以使用开放的地下通道在任意两栋房屋之间移动。
- 教师不应居住在由通道直接连接的房屋中。
请主办方帮助选择教师居住的房屋,以满足安全要求或确定不可能。
输入
第一个输入行包含一个整数 $$$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
注意
下图显示了第二个示例测试。