#include <bits/stdc++.h>
#define int long long
#define fin(x) freopen (x,"r",stdin)
#define fout(x) freopen (x,"w",stdout)
#define reg(i,x,y) for (register int i=(x);i<=(y);++i)
#define Reg(i,x,y) for (register int i=(y);i>=(x);--i)
using namespace std;
int n,m;
struct edge{
	vector<int> a;
	inline int size () {return a.size ();}
	inline void push (int x) {a.push_back (x);}
	inline int operator[] (int i) {return a[i];}
	inline void edge_sort () {sort (a.begin (),a.end ());}
	edge () {a.resize (0);}
};
vector<edge> a (1);
vector<bool> b (1);
inline int read (void) {int x=0,f=0;char ch=getchar ();while (!isdigit (ch)) {f|=(ch=='-');ch=getchar ();}while (isdigit (ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar ();return f?-x:x;}
inline void write (int x) {if (x<0) putchar ('-'),x=-x;if (x>9) write (x/10);putchar (x%10|48);}
inline void write_ (int x) {write (x);putchar (' ');}
inline void dfs (int x)
{
	write_ (x);
	b[x]=true;
	reg (i,0,a[x].size ()-1)
		if (!b[a[x][i]]) b[a[x][i]]=true,dfs (a[x][i]);
}
inline void bfs (int x)
{
	queue<int> q;
	q.push (x);
	b[x]=true;
	while (!q.empty ())
	{
		x=q.front ();
		write_ (x);
		reg (i,0,a[x].size ()-1)
			if (!b[a[x][i]]) b[a[x][i]]=true,q.push (a[x][i]);
		q.pop ();
	}
}
signed main ()
{
	n=read (),m=read ();
	a.resize (n+1);
	b.resize (n+1);
	reg (i,1,m)
	{
		int x=read (),y=read ();
		if (x!=y)
			a[x].push (y);
	}
	reg (i,1,n) a[i].edge_sort ();
	reg (i,1,n)
		if (!b[i])
			dfs (i);
	putchar ('\n');
	reg (i,1,n) b[i]=false;
	reg (i,1,n)
		if (!b[i])
			bfs (i);
	putchar ('\n');
	return 0;
}