#include <bits/stdc++.h>
using namespace std;
int n,m,xx,yy,y,l,sum;
vector <int> a[100005];
vector <int> c;
int b[100005];
void dfs(int x){
	cout << x << " ";
	b[x]=1;
	for(int i=0;i<a[x].size();i++){
		y=a[x][i];
		if(b[y]==0)dfs(y);
	}
}
void bfs(){
	int x; l=0; b[1]=1;
	c.push_back(1); cout << "1 ";
	while(c.size()!=n){
		sum=0;
		for(int i=l;i<c.size();i++){
			x=c[i];
			for(int j=0;j<a[x].size();j++){
				y=a[x][j];
				if(b[y]==0){
					cout << y << " ";b[y]=1;c.push_back(y);sum++;
				}
			}
		}
		l+=sum;
	}
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> xx >> yy;
		a[xx].push_back(yy);
	}
	for(int i=1;i<=n;i++){
		sort(a[i].begin(),a[i].end());
	}
	memset(b,0,sizeof(b));
	dfs(1);
	cout << "\n";
	memset(b,0,sizeof(b));
	bfs();
}

rt