#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>

#include<cstring>
const int N = 1e6 + 7;
using namespace std;
vector<int>adj[N];
int vis[N];
int n, m;
void dfs(int x) {
    stack<int>st;
    st.push(x);
    vis[x] = 1;
    while (!st.empty()) {
        int p = st.top();
        cout << p << " ";
        st.pop();

        for (auto v : adj[p]) {
            if (!vis[v]) {
                vis[v] = 1;
                st.push(v);
            }
        }

    }

}
void bfs(int x) {
    memset(vis, 0, sizeof(vis));
    queue<int>q;
    q.push(x);
    vis[x] = 1;
    cout << x << " ";
    while (!q.empty()) {
        int p = q.front();
        q.pop();

        for (auto v : adj[p]) {
            if (!vis[v])
            {
                cout << v << " ";
                q.push(v);
                vis[v] = 1;
            }
        }
    }
}
int main() {

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {

        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)
    {
        sort(adj[i].begin(), adj[i].end(), greater<int>());
    }
    dfs(1);
    cout << endl;

    for (int i = 1; i <= n; i++)
    {
        sort(adj[i].begin(), adj[i].end());
    }
    bfs(1);
    cout << endl;
}

谢谢哥