#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 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; }

//别人的
#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;
}