Cho một cây có \(n\) đỉnh, đỉnh gốc là \(1\). Mỗi đỉnh được nối với nhau bởi \(n - 1\) cạnh, biểu diễn một cây vô hướng.

Một Euler Tour trên cây là một trình tự các đỉnh mà chúng ta có thể thu được bằng cách duyệt cây theo phương pháp DFS (Depth First Search), bắt đầu từ đỉnh gốc. Mỗi đỉnh sẽ được ghi lại hai lần trong Euler Tour: một lần khi đi vào đỉnh và một lần khi quay lại đỉnh từ các nút con của nó.

Nhiệm vụ của bạn là thực hiện duyệt Euler Tour trên cây và in ra trình tự các đỉnh theo thứ tự Euler Tour.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\) — số đỉnh của cây.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u,v \le n, u \neq v)\), biểu diễn một cạnh giữa đỉnh \(u\) và đỉnh \(v\).

Dữ liệu ra

In ra Euler Tour của cây, gồm \(2n-1\) số nguyên, biểu diễn trình tự các đỉnh theo thứ tự Euler Tour.

Input 1

5
1 2
1 3
2 4
2 5

Output 1

1 2 4 2 5 2 1 3 1

Giải thích

        1
       / \
      2   3
     / \
    4   5

Euler Tour của cây này là: 1 -> 2 -> 4 -> 2 -> 5 -> 2 -> 1 -> 3 -> 1

Input 2

3
1 2
1 3

Output 2

1 2 1 3 1