题干：

The 44th World Finals of the International Collegiate Programming Contest (ICPC 2020) will be held in Moscow, Russia. To celebrate this annual event for the best competitive programmers around the world, it is decided to host a welcome party for all  participants of the World Finals, numbered from  to  for convenience.

The party will be held in a large hall. For security reasons, all participants must present their badge to the staff and pass a security check in order to be admitted into the hall. Due to the lack of equipment to perform the security check, it is decided to open only one entrance to the hall, and therefore only one person can enter the hall at a time.

Some participants are friends with each other. There are  pairs of mutual friendship relations. Needless to say, parties are more fun with friends. When a participant enters the hall, if he or she finds that none of his or her friends is in the hall, then that participant will be unhappy, even if his or her friends will be in the hall later. So, one big problem for the organizer is the order according to which participants enter the hall, as this will determine the number of unhappy participants. You are asked to find an order that minimizes the number of unhappy participants. Because participants with smaller numbers are more important (for example the ICPC director may get the number 1), if there are multiple such orders, you need to find the lexicographically smallest one, so that important participants enter the hall first.

Please note that if participant  and  are friends, and if participant  and  are friends, it's NOT necessary that participant  and  are friends.

Input

There are multiple test cases. The first line of the input contains a positive integer , indicating the number of cases. For each test case:

The first line contains two integers  and  (), the number of participants and the number of friendship relations.

The following  lines each contains two integers  and  (), indicating that the -th and the -th participant are friends. Each friendship pair is only described once in the input.

It is guaranteed that neither the sum of  nor the sum of  of all cases will exceed .

Output

For each case, print a single integer on the first line, indicating the minimum number of unhappy participants. On the second line, print a permutation of  to separated by a space, indicating the lexicographically smallest ordering of participants entering the hall that achieves this minimum number.

Consider two orderings  and , we say  is lexicographically smaller than , if there exists an integer  (), such that  holds for all , and .

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Sample Input

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

Sample Output

1
1 2 3 4
2
1 2 3 4

题目大意：有n个人m个关系，每一对关系代表这两人认识，关系不具有传递性，现在你要安排这n个人进入一个舞会，如果第i个人进入了舞会大厅但是发现没有一个认识的人，那就会不高兴。问你怎么安排顺序这n个人进入舞会大厅，使得不开心的人数最少。如果有多种方案，输出字典序最小的方案。

解题报告：

  首先每一个连通块肯定有一个人是不开心的，并且可以做到只有一个人是不开心的，所以有多少连通块，就有多少人不开心。对于字典序，只需要搞个优先队列遍历就可以了。然后因为有多个连通块，肯定不能一个块一个块的遍历，所以需要弄一个超级源点连到所有的起点上，然后再遍历，注意连到每个联通块的起点，这个起点需要是整个块的最小值，这样肯定使得结果最优。而让块的祖先节点是最小值，这一点可以用并查集稍作修改实现。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e6 + 5;
int f[MAX],n,m;
int getf(int v) {
	return f[v] == v ? v : f[v] = getf(f[v]);
}
void merge(int u,int v) {
	int t1 = getf(u);
	int t2 = getf(v);
	if(t1>t2) f[t1] = t2;
	else f[t2]=t1;
}
int ans[MAX],tot,vis[MAX];
vector<int> vv[MAX];
void bfs(int st) {
	priority_queue<int,vector<int>,greater<int> > pq;
	pq.push(st);
	while(!pq.empty()) {
		int cur = pq.top();pq.pop();
		if(vis[cur] == 1) continue;
		vis[cur] = 1;
		ans[++tot] = cur;
		int up = vv[cur].size();
		for(int i = 0; i<up; i++) {
			int v = vv[cur][i];
			if(vis[v]) continue;
			pq.push(v);
		}
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		tot=0;
		scanf("%d%d",&n,&m);
		for(int i = 0; i<=n; i++) f[i] = i,vv[i].clear(),vis[i]=0;
		for(int u,v,i = 1; i<=m; i++) {
			scanf("%d%d",&u,&v);
			vv[u].pb(v);vv[v].pb(u);
			merge(u,v);
		}
		int ans1 = 0;
		for(int i = 1; i<=n; i++) {
			if(f[i] == i) vv[0].pb(i),ans1++;
		}
		bfs(0);
		printf("%d\n",ans1);
		for(int i = 2; i<=tot; i++) {
			printf("%d%c",ans[i],i==tot ? '\n': ' ');
		}
	}
	return 0 ;
}