//P5318
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
bool dfsvis[100005],bfsvis[100005];
vector<int> pic[100005];

void dfs(int n){
    printf("%d ",n);
    for(int i=0; i<pic[n].size(); ++i)
        if(!dfsvis[pic[n][i]]){
            dfs(pic[n][i]);
            dfsvis[pic[n][i]]=true;
        }
    return;
}
void bfs(int n){
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        int t=q.front();
        printf("%d ",t);
        q.pop();
        for(int i=0; i<pic[t].size(); ++i){
            if(!bfsvis[pic[t][i]]){
                q.push(pic[t][i]);
                bfsvis[pic[t][i]]=true;
            }
        }
    }
    return;
}

int main(){
    int n,m,a,b;
    scanf("%d %d",&n,&m);
    for(int i=0; i<m; ++i){
        scanf("%d %d",&a,&b);
        pic[a].push_back(b);
    }
    for(int i=1; i<=n; ++i)
        sort(pic[i].begin(),pic[i].end());
    dfsvis[1]=true;
    bfsvis[1]=true;
    dfs(1);
    printf("\n");
    bfs(1);
    return 0;
}

求助