Lesson22

#include <iostream>
using namespace std;
struct Node {
  int Data;
  Node* Left = nullptr;
  Node* Right = nullptr;
};

void DFS(Node* node) {
  cout << node->Data << " ";
  if (node->Left) {
    DFS(node->Left);
    cout << node->Data << " ";
  }
  if (node->Right) {
    DFS(node->Right);
    cout << node->Data << " ";
  }
}

int main1() {
  Node* root = nullptr;
  int x;
  while (cin >> x, x != 0) {
    if (!root) {
      root = new Node();
      root->Data = x;
      continue;
    }
    Node* node = root;
    while (true) {
      if (node->Data == x) break;
      if (node->Data < x) {
        if (node->Right == nullptr) {
          node->Right = new Node();
          node->Right->Data = x;
          break;
        }
        node = node->Right;
      } else {
        if (node->Left == nullptr) {
          node->Left = new Node();
          node->Left->Data = x;
          break;
        }
        node = node->Left;
      }
    }
  }
  DFS(root);
  return 0;
}

void PreOrderDFS(vector<vector<int>>& t, int u, int p) {
  cout << u << "\n";
  for (int v : t[u]) {
    if (v != p)
      PreOrderDFS(t, v, u);
  }
}

int main() {
  int n; cin >> n;
  vector<vector<int>> t(n + 1);
  for (int i = 0; i < n - 1; ++i) {
    int u, v; cin >> u >> v;
    t[u].push_back(v);
    t[v].push_back(u);
  }
  PreOrderDFS(t, 1, -1);
}