Particle Accelerator

Time limit5sMemory limit2048 MB

Summary

The accelerator is a tree of N rooms, and the task makes Q calls to generate with distinct room values v, but the statement never says what generate must return.

Level: Medium5 of 10
Topics: Tree, DFS
Solved: No attempts yet

Problem

The KOI research institute runs experiments with a particle accelerator. The accelerator has $N$ rooms and $N-1$ two-way passages that connect them. Any two distinct rooms can reach each other using only passages, so the accelerator forms a tree.

Rooms are numbered with distinct integers from $0$ to $N-1$ , and passages are numbered with distinct integers from $0$ to $N-2$ . For every $0 \le i \le N-2$ , passage $i$ connects room $A[i]$ and room $B[i]$ .

Constraints

$2 \le Q \le N \le 200\,000$
The accelerator forms a tree.
For all $i$ , $0 \le A[i], B[i] \le N-1$ and $A[i] \neq B[i]$ ( $0 \le i \le N - 2$ ).
For every call to the generate function, $0 \le v \le N-1$ , and each $v$ is a different value.

Examples1

Example 1
Input
```
2 2
0 1
0
1
```
Expected output
```
0
1
```