#include<bits/stdc++.h>
#define N 100010

using namespace std;

int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
	{
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
	{
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}

vector <int> g[N];
int n,m;
bool f[N];

void dfs(int u)
{
	cout << u << " ";
	if (f[u]) return ;
	f[u] = true;
	for (int i=0;i<g[u].size();i++)
		if (!f[g[u][i]]) dfs(g[u][i]);
}

void bfs(int u)
{
	queue <int> q;
	q.push(u);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		cout << x << " ";
		for (int i=0;i<g[x].size();i++)
			if (!f[g[x][i]])
			{
				q.push(g[x][i]);
				f[g[x][i]] = true;
			}
	}
}

int main()
{
	n=read(),m=read();
	for (int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		sort(g[i].begin(),g[i].end());
	dfs(1);
	cout << endl;
	memset(f,false,sizeof(f));
	bfs(1);
	cout << endl;
	return 0; 
}

样例过了，#1 AC，其他 WA。