#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 = 1e3;
int N, M, sum, cnt;
int g[MAXX][MAXX], flag[MAXX];
std:: queue <int> q;

void dfs(int x){
	if(x==1) printf("%d",x);
	else printf("-%d",x);
	sum++;
	flag[x] = 1;
	for(int i=1;i<=N;i++){
//		if(!g[x][i]) continue;
//		if(flag[i]) continue;
		if(g[x][i] && (!flag[i])) dfs(i);
	}
}

int main(){
	N = read(), M = read();
	for(int i=1;i<=M;i++){
//		int x = read(), y = read();
		int x,y;
		cin>>x>>y;
		g[x][y] = 1;
	}
	dfs(1);
	while(sum+1<=N){
		dfs(sum);
	};
	printf("\n");
	memset(flag,0,sizeof(flag));
	q.push(1);
	flag[1] = 1;
	while(!q.empty()){
		int F = q.front();
		for(int i=1; i<=N; i++){
			if(g[F][i]==1 && (flag[i]==0)){
				q.push(i);
				flag[i] = 1;
			}
		}
		if(F==1) printf("%d",F);
		else printf("-%d",F);
		q.pop();
		cnt++;
	}
	while(cnt<=N){
		while(!q.empty()){
			int F = q.front();
			for(int i=1; i<=N; i++){
				if(g[F][i]==1 && (flag[i]==0)){
					q.push(i);
					flag[i] = 1;
				}
			}
			if(F==1) printf("%d",F);
			else printf("-%d",F);
			q.pop();
			cnt++;
		}
	}
//	for(int i=1;i<=N;i++){
//		for(int j=1;j<=N;j++){
//			printf("%d ",g[i][j]);
//		}
//		printf("\n");
//	}
	return 0;
}