P3549 [POI 2013] MUL-Multidrink

**This translation is AI-generated.**

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.

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$.

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$.

Translated by ChatGPT 5