Meeting Point

$N$ friends each live on their own node of a tree with $N$ nodes, where $N$ is odd. A tree is a connected graph with exactly $N-1$ edges.

The friends want to meet at one node of the tree. They have decided to meet at the node that minimizes the sum of distances to all friends, and they asked you to find this optimal meeting point. The distance $\text{dist}(a,b)$ between two nodes $a$ and $b$ is the number of edges on the path between them. Formally, you want to find the node $x$ that minimizes $\sum_{i=1}^{n} \text{dist}(x,i)$.

The friends do not remember what the tree looks like. They do remember this: given three different friends $a$, $b$, and $c$, they meet (when only those three are present) at the node $x$ that minimizes $\text{dist}(x,a)+\text{dist}(x,b)+\text{dist}(x,c)$. Note that $x$ is not necessarily one of $a$, $b$, or $c$.

The tree is not given in the input. You may ask up to $Q-1$ questions of the form: where do friends $a$, $b$, and $c$ meet? Use these questions to find the optimal meeting point.

Illustration of the example tree. Node 2 is the optimal meeting point.

$3 \le N\le 24\,999$