Pleasant Tour

The largest amusement park in Jakarta has $N$ rides, numbered from 0 to $N-1$. The rides are connected by $N-1$ two-way paths, so for any two rides there is exactly one path between them. The paths are numbered from 0 to $N-2$. Path $i$ connects rides $A[i]$ and $B[i]$, and walking along it takes one hour. To avoid crowding, every ride is connected to at most 3 paths.

You want to build a tour that visits every ride exactly once. Walking through several paths to get from one ride to the next is tiresome. To make the tour pleasant, the travel time from each ride to the next must not be longer than the travel time of the step before it. In other words, find a permutation $P[0], P[1], \dots, P[N-1]$ of the integers from 0 to $N-1$ such that for every $0 < i < N-1$, the time to walk from $P[i]$ to $P[i+1]$ is not greater than the time to walk from $P[i-1]$ to $P[i]$.

You do not have the full map. You can ask the information center up to $Q$ questions. Each question has two parameters $X$ and $Y$, where $0 \le X, Y < N$. A question is one of the following two kinds.

• How many hours does it take to walk from ride $X$ to ride $Y$? When $X = Y$, the answer is 0.
• Given $X$ and $Y$, how many rides $Z$ satisfy this condition: to walk from ride $X$ to ride $Z$, you must pass through ride $Y$? Ride $Y$ is included. When $X = Y$, the answer is $N$.

• $2 \le N \le 100000$.
• $Q = 400000$.
• Any two rides can reach each other through the paths.
• Each ride is connected to at most 3 paths. (That is, it is an endpoint of at most 3 paths.)