#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,b[100010],c[100010],b1[100010];
vector<int> a[100010];
void qsort(int k,int l,int r)
{
	if(l>=r) return;
	int i=l,j=r,mid=a[k][(l+r)/2];
	while(i<=j)
	{
		while(a[k][i]<mid) i++;
		while(mid<a[k][j]) j--;
		if(i<=j)
		{
			swap(a[k][i],a[k][j]);
			i++;j--;
		}
	}
	if(l<j) qsort(k,l,j);
	if(i<r) qsort(k,i,r);
}
void dfs(int k)
{
	printf("%d ",k);
	if(a[k].size()==0) return;
	for(int i=0;i<=a[k].size()-1;i++) if(!b[a[k][i]]) b[a[k][i]]=1,dfs(a[k][i]);
} 
void bfs(int k)
{
	int h=0,t=1;c[1]=k;
	while(h<t)
	{
		h++;
		printf("%d ",c[h]);
		if(a[c[h]].size()==0) continue;
		for(int i=0;i<=a[c[h]].size()-1;i++)
		{
			if(!b1[a[c[h]][i]])
			{
				t++;
				c[t]=a[c[h]][i];
				b1[a[c[h]][i]]=1;
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
	}
	for(int i=1;i<=n;i++) qsort(i,0,a[i].size()-1);
	b[1]=1;
	dfs(1);
	cout<<endl;
	b1[1]=1;
	bfs(1);
}