Description

Byteasar lives in Byteburg, a city famous for having a milk bar on every street corner. One day, he came up with a “multidrink plan”: he wants to visit each milk bar exactly once. Ideally, he wants to design a route such that the distance from the previous milk bar to the next one is at most 2 edges each time.

The intersections of Byteburg are numbered from $1$ to $N$, and all streets are bidirectional. Between every pair of intersections, there is a unique simple path (i.e., a path that does not visit any intersection more than once). Byteasar will start at intersection $1$ and finish at intersection $N$. Your task is to find any route that satisfies his requirement, if it exists.

Input Format

The first line contains an integer $N$ ($2 \leq N \leq 500000$), the number of intersections in Byteburg. Each of the next $N - 1$ lines contains a pair of distinct integers $A_i$ and $B_i$ ($1 \leq A_i, B_i \leq N$), describing a street connecting intersections $A_i$ and $B_i$.

Output Format

If no such route exists, output a single word “BRAK” (Polish for “none”) without quotes. Otherwise, output $N$ lines; the $i$-th line should contain the index of the $i$-th intersection on the route. In this case, the first line must be $1$, and the last line must be $N$.

12
1 7
7 8
7 11
7 2
2 4
4 10
2 5
5 9
2 6
3 6
3 12

1
11
8
7
4
10
2
9
5
6
3
12

Hint

Translated by ChatGPT 5