#include<bits/stdc++.h>
using namespace std;
struct edge{
	int nxt,to;
}mp[1000005];
vector<int> v[1000005];
int n,m,tot;
int head[1000005];
int vis[1000005];
int wcnm[1000005];
void add(int u,int v){
	mp[++tot].to = v;
	mp[tot].nxt = head[u];
	head[u] = tot;
	return ;
}
void bfs(int x){
	queue<int> q;
	q.push(x);
	vis[x] = 1;
	while(!q.empty()){
		int t = q.front();
		printf("%d",t);
		q.pop();
		int len = v[t].size();
		for(int i = 0;i < len;i++){
			if(!vis[v[t][i]]){
				q.push(v[t][i]);
				vis[v[t][i]] = 1;
			}
		}
	}
	return ;
}
void dfs(int x){
	printf("%d",x);
	int len = v[x].size();
	for(int i = 0;i < len;i++){
		if(!wcnm[v[x][i]]){
			wcnm[v[x][i]] = 1;
			dfs(v[x][i]);
		}
	}
	return ;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int u,sb;
		scanf("%d%d",&u,&sb);
		v[u].push_back(sb);
	}
	wcnm[1] = 1;
	dfs(1);
	printf("\n");
	bfs(1);
	return 0;
}