万瓦鳞鳞若火龙,日车不动汗珠融 无因羽翮氛埃外,坐觉蒸炊釜甑中
刚好younik觉得自己的小麦色皮肤最近褪色了,所以她决定今天去校医院做检测,顺便在路上把自己晒黑(陕师大集训队提醒您:天气炎热,出门请做好防晒工作)。
younik好不容易到了校医院,发现校医院居然还没有开门,大家都站在门口。younik看到了自己的几个好友,她上前一问,发现每个人手里都拿了一个号码牌,号码牌是按照从小到大的顺序排号的。
这时候校医院开门了,负责人帅气的王老师走了出来,他说:“大家都知道,疫情期间两个人不能靠得太近,于是校医院一次只允许一个人进门。”
和朋友们一起做检测很明显更加的快乐,如果有个同学进了校医院却发现她的朋友没在校医院里,那么她会很难过(哪怕她的朋友待会进来)。
帅气的王老师不希望看到难过的人太多,所以他希望找到一个序列,让难过的人最少。帅气的王老师也是一个公平的王老师,他说:“因为最先来的人等的时间最久,所以如果难过的人数最少的序列有很多个,那么最先来的人要先进入校医院。”
你是是个心地善良的小朋友,你一定不忍心看到帅气的王老师因为想不出序列而掉光头发,所以你决定写个程序帮帮他(强行按头帮忙)。
有很多案例,输入的第一行包含一个正整数T,表示案例数。对于每个测试用例:
第一行包含两个整数n和m(2<=n<=1e6,1<=m<=1e6),分别表示了在门口排队的人的数量和友谊对的数量。接下来会输入m行,每一行都包含两个整数a和b(1<=a,b<=n),表示第a个和第b个正在排队的人是朋友。每个友谊对在输入中只描述一次。 保证所有案例的总和都不会超过1e6。保证不会输入a和a是朋友的情况。
对于每个用例,需要输出两行。第一行表示不高兴的人数,第二行是大家进入校医院的顺序(用空格隔开),表示进入校医院的人中不高兴的人数达到这个数的字典最小顺序。