#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
int n,m,cnt,head[1000005],vis[1000005],bfs[1000005];
pair<int,int> x[1000005];
struct edge{
	int to,nextt;
}edge[100005];
//priority_queue<pair,vector<pair<int,int>>,greater<pair<int,int>>>
int in(){int k=0,f=1;char c=getchar();while (c<'0'||c>'9'){if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}return k*f;}
void addedge(int z)
{
	cnt++;
	edge[cnt].to=x[z].second;
	edge[cnt].nextt=head[x[z].first];
	head[x[z].first]=cnt;
}
void dfs(int z)
{
	cout<<z<<" ";
	vis[z]=true;
	for (int i=head[z];i;i=edge[i].nextt)
	{
		if (!vis[edge[i].to])
		{
			dfs(edge[i].to);
		}
	}
}
//_unlocked
signed main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>x[i].first>>x[i].second;
	}
	sort(x+1,x+m+1);
	for (int i=m;i>=1;i--)
	{
		addedge(i);
	}
	dfs(1);
	cout<<endl;
	for (int i=1;i<=n;i++) vis[i]=false;
	int pos=1,r=0,p=0;
	while (pos>0)
	{
		cout<<pos<<" ";
		vis[pos]=true;
		for (int i=head[pos];i;i=edge[i].nextt)
		{
			if (!vis[edge[i].to])
			{
				r++;
				bfs[r]=edge[i].to;
				vis[edge[i].to]=true;
			}
		}
		p++;
		pos=bfs[p];
	}
	return 0;
}
/*
8 9
3 7
4 7
4 8
7 8
1 4
2 5
2 6
1 2
1 3
*/