#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;
const int maxn = 100005;
struct edge {
   int next, r;
} arr[1000005];
int head[maxn];  //节点i的下一条边
bool b[maxn];
bool b2[maxn];

struct node {
   int now, depth;
   bool operator<(const node& k) const {
      if (depth == k.depth) return now > k.now;  //升序
      return depth > k.depth;                    //升序
   }
};

void dfs(int now) {
   printf("%d ", now);
   b[now] = true;
   vector<int> q;
   for (int i = head[now]; i; i = arr[i].next) {
      if (!b[arr[i].r]) q.push_back(arr[i].r);
   }
   sort(q.begin(), q.end());
   for (size_t i = 0; i < q.size(); i++) {
      if (!b[q[i]]) dfs(q[i]);
   }
}

int main() {
   int l, r;
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= m; ++i) {
      scanf("%d%d", &l, &r);
      arr[i].r = r;
      arr[i].next = head[l];
      head[l] = i;
   }

   int starthead = 1;
   // dfs
   dfs(starthead);
   putchar('\n');

   // bfs
   int depth = 0;
   priority_queue<node> q;
   q.push({starthead, depth});
   while (!q.empty()) {
      node tem = q.top();
      q.pop();
      printf("%d ", tem.now);
      b[tem.now] = true;
      for (int i = head[tem.now]; i; i = arr[i].next) {
         if (!b2[arr[i].r]) {
            q.push({arr[i].r, tem.depth + 1});
            b2[arr[i].r] = true;
         }
      }
   }
   return 0;
}

初始化vis[1]为1了，还是错了后四个…… 是哪些细节没注意吗