DeveloperOC

#include <iostream>
#include <map>
#include <set>
using namespace std;

int N, M, V;

struct Node {
public:
  void push(int n) { lines.emplace(n); }
  bool isContain(int n) { return lines.find(n) != lines.end(); }
  void setDFS() { isDFS = true; }
  bool getDFS() { return isDFS; }
  void setBFS() { isBFS = true; }
  bool getBFS() { return isBFS; }

private:
  set<int> lines;
  bool isDFS = false, isBFS = false;
};

map<int, Node> graph;

void dfs(int root) {
  cout << root;
  graph[root].setDFS();
  for (int i = 1; i <= N; ++i) {
    if (graph[root].isContain(i) == false)
      continue;
    if (graph[i].getDFS())
      continue;

    cout << " ";
    dfs(i);
  }
  return;
}

void bfs(int root) {
  int target[1001] = {0};
  target[0] = root;
  int cnt = 0;
  int index = 1;
  while (target[cnt] != 0) {
    cout << target[cnt];
    graph[target[cnt]].setBFS();
    for (int i = 1; i <= N; ++i) {
      if (graph[target[cnt]].isContain(i) == false)
        continue;
      if (graph[i].getBFS())
        continue;
      if (index >= N)
        break;
      graph[i].setBFS();
      target[index] = i;
      index++;
    }
    cnt++;

    if (target[cnt] == 0)
      return;
    cout << " ";
  }
  return;
}

int main() {
  cin >> N >> M >> V;

  for (int i = 1; i <= N; ++i) {
    graph.emplace(i, Node());
  }

  for (int i = 0; i < M; ++i) {
    int key, value;
    cin >> key >> value;
    graph[key].push(value);
    graph[value].push(key);
  }

  dfs(V);
  cout << '\n';
  bfs(V);
  return 0;
}