#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MANX 100005
using namespace std;
int m,n;
struct edge {
    int from,to;
};
bool cmp(edge a,edge b){
    if(a.from==b.from)return a.to < b.to;
    return a.from<b.from;
}
vector<edge>edges;
vector<vector<int>>graph;
bool vis[MANX];
queue<int>q;
void dfs(int x){
    cout<<x<<' ';
    for (int i = 0; i < graph[x].size(); i++) {
        if(!vis[graph[x][i]]){
            vis[graph[x][i]]=true;
            dfs(graph[x][i]);
        }
    }
}

void bfs(){
    while (!q.empty()) {
        int x=q.front();
        q.pop();
        cout<<x<<' ';
        for (int i = 0; i < graph[x].size(); i++) {
            if(!vis[graph[x][i]]){
                vis[graph[x][i]]=true;
                q.push(graph[x][i]);
            }       
        }     
    }
    
}
int main(){ 
    cin>>n>>m;
    graph.resize(n+1);
    for (int i = 0; i <m; i++) {
        int from,to;
        cin>>from>>to;
        edges.push_back({from,to});     
    }
    sort(edges.begin(),edges.end(),cmp);
    for (int i = 0; i < m; i++) {
        graph[edges[i].from].push_back(edges[i].to);
    }
    
    
    vis[1]=true;
    dfs(1);
    cout<<endl;
    memset(vis,false,sizeof(vis));
    
    vis[1]=true;
    q.push(1);
    bfs();
    return 0;
    
}

qwq，如果可以的话想知道怎么样的样例会错