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();   // 들어오자마자 방문 처리 (재귀 무한루프 방지)

  // 1번부터 훑으므로 "번호가 작은 정점 먼저" 조건이 자연스럽게 지켜진다
  for (int i = 1; i <= N; ++i) {
    if (graph[root].isContain(i) == false)
      continue;           // root와 i 사이에 간선이 없음
    if (graph[i].getDFS())
      continue;           // 이미 방문한 정점

    cout << " ";
    dfs(i);               // 더 깊이 내려간다
  }
  return;
}

void bfs(int root) {
  // queue 대신 배열을 큐처럼 쓴다.
  // 정점 번호가 1부터라서 0을 "비어있음" 표시로 쓸 수 있다.
  int target[1001] = {0};
  target[0] = root;
  int cnt = 0;      // 큐에서 꺼낼 위치 (front)
  int index = 1;    // 큐에 넣을 위치 (rear)

  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++;

    // 다음에 꺼낼 자리가 비었으면 = 큐가 비었으면 종료.
    // 여기서 return 해야 마지막 정점 뒤에 공백이 붙지 않는다.
    if (target[cnt] == 0)
      return;
    cout << " ";
  }
  return;
}

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

  // 간선이 하나도 없는 정점도 map에 있어야 조회가 안전하다
  for (int i = 1; i <= N; ++i) {
    graph.emplace(i, Node());
  }

  for (int i = 0; i < M; ++i) {
    int key, value;
    cin >> key >> value;
    // 양방향 간선이므로 양쪽에 모두 등록.
    // lines가 set이라 중복 간선은 자동으로 무시된다.
    graph[key].push(value);
    graph[value].push(key);
  }

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