1563题的题解
#include<bits/stdc++.h>
using namespace std;

int read(){
	int ans = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		f = (ch=='-') ? -1 : 1;
		ch = getchar();
	}
	while(isdigit(ch)){
		ans = (ans<<1)+(ans<<3)+(ch^48);
		ch = getchar();
	}
	return ans*f;
}

const int MAXX = 5e3;
int n, m, sum;
int g[MAXX][MAXX], flag[MAXX];

void dfs(int x){
	if(sum>n) return;
	sum++;
	flag[x] = 1;
	if(x == 1) printf("1");
	else printf("-%d",x);
	int t = 0;
	for(int i=1; i<=n; i++){
		if(g[x][i]==1 && (!flag[i])){
			dfs(i);
		}
	}
}

queue <int> q;

void bfs(){
	flag[1] = 1;
	q.push(1);
	sum++;
	while(sum<n){
		if(q.empty()){
			for(int i=1; i<=n; i++){
				if(!flag[i]){
					q.push(i);
					flag[i] = 1;
					sum++;
				}
			}
		}
		int x = q.front();
		for(int i=1; i<=n; i++){
		if(g[x][i]==1 && (!flag[i])){
			q.push(i);
			flag[i] = 1;
			sum++;
			}
		}
		if(x == 1) printf("1");
		else{
			printf("-%d", q.front());
		}
		q.pop();
	}
	while(!q.empty()){
		printf("-%d",q.front());
		q.pop();
	}
	return;
}

int main(){
	n = read(), m = read();
	memset(g, 0x3f, sizeof(g));
	for(int i=1; i<=m; i++){
		int a =  read(), b = read();
		g[a][b] = 1 ;
		g[b][a] = 1 ;
	}
	for(int i=1; i<=n; i++){
		g[i][i] = 0;
	}
	dfs(1);
	while(sum<n){
		for(int i=1; i<=n; i++){
			if(!flag[i]) dfs(i);
		}
	}
	cout<<endl;
	memset(flag, 0, sizeof(flag));
	sum = 0;
	bfs();
	return 0;
}