#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000000+5;
int n,m;
int v[MAXN];
vector<int> a[MAXN];
bool cmp(int x,int y)
{
	return x<y;
}
void dfs(int x,int cnt)
{
	cnt++;
	cout<<x<<" ";
	if(cnt==n) return ;
	for(int i=0;i!=a[x].size();i++)
	{
		int nx=a[x][i];
		if(!v[nx])
		{
			v[nx]=1;
			dfs(nx,cnt);
//			v[nx]=0;
		}
		
			
	} 
}
void bfs()
{
	queue<int> q;
	q.push(1);
	v[1]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		cout<<x<<" ";
		for(int i=0;i!=a[x].size();i++)
		{
			int nx=a[x][i];
			if(!v[nx])
			{
				v[nx]=1;
				q.push(nx);
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
		sort(a[i].begin(),a[i].end(),cmp);
	memset(v,0,sizeof(v));
	dfs(1,0);
	cout<<endl;
	memset(v,0,sizeof(v));
	bfs();
	cout<<endl;
	return 0;
}

谢谢啦