{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"第44届国际大学生编程竞赛世界决赛(ICPC 2020)将在俄罗斯莫斯科举行。 为了庆祝这一年度活动,以吸引全球最有竞争力的程序员,我们决定为所有n名世界总决赛参与者举办欢迎晚会,为方便起见,人数标记从1到n。 派对将在一个大厅举行。 出于安全原因,所有参与者都必须向工作人员出示证章并通过安全检查,才能进入大厅。 由于缺乏进行安全检查的设备,因此决定只打开一个进入大厅的入口,因此一次只能一个人进入大厅。 一些参与者是彼此的朋友。 相互之间有一对友好关系。 不用说,与朋友聚会更有趣。 当参与者进入大厅时,如果他或她发现他或她的朋友中没有一个不在大厅中,那么即使他或她的朋友以后会在大厅中,该参与者也会感到不高兴。 因此,组织者面临的一个大问题是参加者进入大厅的顺序,因为这将决定不满意的参加者的数量。 要求您找到一个减少不满意参与者人数的顺序。 由于人数较小的参与者更重要(例如编号为1的会员比编号为2的会员重要),因此,如果存在多个这样的命令,则需要找到词典顺序上最小的顺序,以便重要的参与者首先进入大厅。 \n请注意,如果参与者a和b是朋友,并且如果参与者b和c是朋友,则参与者a和c不一定是朋友。\n\u003ch4\u003eInput\u003c/h4\u003e \n多个测试用例。 输入的第一行包含一个正整数 T,表示案例数。 对于每个测试用例:\u003c/ p\u003e\n\n\u003cp\u003e第一行包含两个整数 n 和m ($ 1 \u003c\u003d n,m \u003c\u003d10 ^ 6 ),参与者的数量和友谊关系的数量。\u003c/ p\u003e\n\n\u003cp\u003e以下$ m $行分别包含两个整数a 和 b ($ 1 \u003c\u003d a,b\u003c\u003d n,a ≠ b ),表示第 a 和 第 b个参与者是朋友。 每个友谊对在输入中仅描述一次。\u003c/ p\u003e\n\n\u003cp\u003e保证所有案例的 n 或 m 的总和不会超过 10 ^ 6 。\u003c/ p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e \n对于每种情况,请在第一行上打印一个整数,表示不满意的参与者的最小数量。 在第二行上,打印一个由1到n的空格(由空格隔开)的排列,表明按字典顺序排列的进入大厅的参与者的最小顺序达到了此最小数量。\n\n\n请不要在每行的末尾输出额外的空格,否则您的解决方案可能被认为是不正确的\n\n\u003ch4\u003eSample Input\u003c/h4\u003e \n\u003cpre\u003e2\n4 3\n1 2\n1 3\n1 4\n4 2\n1 2\n3 4\n\u003c/pre\u003e \n\u003ch4\u003eSample Output\u003c/h4\u003e \n\u003cpre\u003e1\n1 2 3 4\n2\n1 2 3 4\n\u003c/pre\u003e"}}]}