Fun Tour of Jakarta Theme Park

In the largest theme park in Jakarta there are $N$ attractions numbered from $0$ to $N-1$. They are connected by $N-1$ bidirectional roads forming a tree – that is, for any two attractions there is a unique simple path between them. The roads are numbered from $0$ to $N-2$. The $i$th road connects attraction $A[i]$ and attraction $B[i]$, and it takes one hour to traverse any road. Moreover, to avoid congestion, every attraction is incident to at most three roads.

You want to find a tour (a permutation $P[0], P[1], \dots, P[N-1]$ of $\{0,1,\dots,N-1\}$) such that every attraction is visited exactly once and the tour is "fun". A tour is fun if the time required to move from $P[i]$ to $P[i+1]$ does not exceed the time required to move from $P[i-1]$ to $P[i]$ for every $0 < i < N-1$, i.e.,

$$d(P[i], P[i+1]) \le d(P[i-1], P[i]) \quad \text{for every } 0 < i < N-1, $$

where $d(u,v)$ is the number of hours needed to travel from attraction $u$ to attraction $v$ (which is equal to the number of roads in the unique simple path between them).

Since you do not have a complete map of the park, you are allowed to make up to $Q$ queries to an information center. Each query is one of two types (parameters $X$ and $Y$ with $0\le X, Y < N$):

• hoursRequired(X, Y): returns the number of hours required to travel from attraction $X$ to attraction $Y$. (Note that if $X=Y$, the answer is $0$.)
• attractionsBehind(X, Y): returns the number of attractions $Z$ such that any route from $X$ to $Z$ will definitely go through $Y$. Here, $Y$ is counted and if $X=Y$, the answer is $N$.

You must implement the function createFunTour(N, Q) that is called exactly once by the judging system. It can use these two query functions and must return a valid permutation (of length $N$) satisfying the fun tour condition.

Note: In our offline simulation (and in the test cases provided), the full map of the park (the tree) is given as input. In other words, after the initial line containing $N$ and $Q$, the next $N-1$ lines each contain two integers representing the attractions connected by a road.

Hint: One way to ensure the condition is to design your tour so that the travel time between successive pairs is constant (or nonincreasing). For example, if you can produce a tour where every two consecutive attractions are adjacent (i.e. travel time 1), then the fun tour condition holds trivially. Unfortunately, a Hamiltonian path with adjacent nodes may not exist in a tree, so you might have to choose a tour in which every move has the same or decreasing travel time. One strategy is to start with two attractions at the endpoints of a diameter, then greedily choose the next unvisited attraction (from the current attraction) with the maximum distance that does not exceed the previous move’s travel time.

inputFormat

The first line contains two integers $N$ and $Q$, representing the number of attractions and the maximum number of queries allowed. Each of the next $N-1$ lines contains two integers $u$ and $v$ (with $0 \le u,v < N$) indicating that there is a bidirectional road between attractions $u$ and $v$.

outputFormat

Output a permutation of $0, 1,\dots, N-1$ (separated by spaces or newlines) representing a valid fun tour, i.e. a sequence $P[0],P[1],\dots,P[N-1]$ such that for each $0 < i < N-1$, $$d(P[i],P[i+1]) \le d(P[i-1],P[i]).$$

sample

4 10
0 1
1 2
2 3

0 3 1 2