younik进入医院
题号:NC210856
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

        大家都知道,最近疫情实在太严重了,大家都人心惶惶的。陕师大的younik也怕得要命,幸好,她得知可以通过核酸检测来判断自己是否患上了病毒。
        今天是一个好日子,正应了陆游写的
万瓦鳞鳞若火龙,日车不动汗珠融 无因羽翮氛埃外,坐觉蒸炊釜甑中

        刚好younik觉得自己的小麦色皮肤最近褪色了,所以她决定今天去校医院做检测,顺便在路上把自己晒黑(陕师大集训队提醒您:天气炎热,出门请做好防晒工作)。

        younik好不容易到了校医院,发现校医院居然还没有开门,大家都站在门口。younik看到了自己的几个好友,她上前一问,发现每个人手里都拿了一个号码牌,号码牌是按照从小到大的顺序排号的。

        这时候校医院开门了,负责人帅气的王老师走了出来,他说:“大家都知道,疫情期间两个人不能靠得太近,于是校医院一次只允许一个人进门。”

        和朋友们一起做检测很明显更加的快乐,如果有个同学进了校医院却发现她的朋友没在校医院里,那么她会很难过(哪怕她的朋友待会进来)。

        帅气的王老师不希望看到难过的人太多,所以他希望找到一个序列,让难过的人最少。帅气的王老师也是一个公平的王老师,他说:“因为最先来的人等的时间最久,所以如果难过的人数最少的序列有很多个,那么最先来的人要先进入校医院。”

        你是是个心地善良的小朋友,你一定不忍心看到帅气的王老师因为想不出序列而掉光头发,所以你决定写个程序帮帮他(强行按头帮忙)。

请注意:如果ab是朋友,bc是朋友,这并不意味着ac是朋友(朋友关系不可传递)。
是所有的朋友都不在才不开心哦!

输入描述:

有很多案例,输入的第一行包含一个正整数T,表示案例数。对于每个测试用例:

第一行包含两个整数n和m(2<=n<=1e6,1<=m<=1e6),分别表示了在门口排队的人的数量和友谊对的数量。

接下来会输入m行,每一行都包含两个整数a和b(1<=a,b<=n),表示第a个和第b个正在排队的人是朋友。每个友谊对在输入中只描述一次。 保证所有案例的总和都不会超过1e6。保证不会输入a和a是朋友的情况。


输出描述:

对于每个用例,需要输出两行。第一行表示不高兴的人数,第二行是大家进入校医院的顺序(用空格隔开),表示进入校医院的人中不高兴的人数达到这个数的字典最小顺序。

示例1

输入

复制
2
4 3
1 2
1 3
1 4
3 1
1 3

输出

复制
1
1 2 3 4
2
1 2 3