#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std ;
vector<int> g[100010] ;//邻接表
vector<bool> vis ;//visit 访问
void dfs(int idx)//深度优先
{
    vis[idx] = 1 ;
    cout << idx << " " ;
    sort(g[idx].begin() , g[idx].end()) ;//排序
    for(auto v: g[idx])
    {
        if(vis[v])
            continue ;
        
        dfs(v) ;//递归
    }
}
void bfs()//广度优先
{
    cout << '\n' ;
	queue<int> q ;
    q.push(1) ;
    while(!q.empty())
    {
        int x = q.front() ;
        sort(g[x].begin() , g[x].end()) ;
        for(auto v: g[x])
        {
            if(vis[v])
                continue ;
            vis[v] = 1 ;
            q.push(v) ;
        }
        cout << x << " " ;
        q.pop() ;
    }
}
int main()
{
    int n , m ;
    cin >> n >> m ;
    for(int i = 0 ; i <= n + 1 ; i ++)
        vis.push_back(0) ;
    for(int i = 0 ; i < m ; i ++)
    {
        int x , y ;
        cin >> x >> y ;
        g[x].push_back(y) ;
    }
    dfs(1) ;
    //vis要清零
    for(int i = 0 ; i <= n + 1 ; i ++)
        vis[i] = 0 ;
    bfs() ;
    return 0 ;
}
/*
备注：
20分（2，3，4，5测试点WA）
有改法的私信我（8133wt5）
*/