Changing Colors

Your friend has a connected graph with $N$ vertices and $N-1$ edges, meaning that the graph is a tree -- there is a unique path between any two nodes.
They secretly choose two distinct favorite nodes, $A$ and $B$, such that the distance between them is at least $2$.
The vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $N - 1$.

You play a guessing game to discover which two nodes your friend picked. In a single question, you can color each edge of the graph either black or white. Your friend then responds with a number: the number of color changes along the unique path from $A$ to $B$.

Formally, let the path from $A$ to $B$ be $A = v_0, v_1, v_2, \ldots, v_k = B$, with $k \geq 2$. The response is the number of inner nodes $v_i$ ($1 \le i < k$) such that the colors of edges $(v_{i-1},v_i)$ and $(v_i,v_{i+1})$ are different.

You may ask up to $31$ questions. If you ask more, your friend will get bored and stop playing. Your task is to determine the hidden nodes $A$ and $B$ using at most $31$ questions.

Implementation

Your task is to implement the following function:

std::pair<int, int> find_nodes(int N, const std::vector<std::pair<int, int>>& edges);

• int N: the number of vertices in the graph.
• edges: a vector of $N-1$ pairs, where edges[i] = \{X_i, Y_i\} means that edge $i$ connects vertex $X_i$ to $Y_i$.
• returns a pair of integers (A, B) — the two favorite nodes your friend picked. The order does not matter.

Interaction

You may ask up to 31 questions using the following function:

int query(const std::vector<int>& colors);

• The colors vector must be of length $N-1$, where colors[i] is the color of edge $i+1$: 0 for white and 1 for black.
• The function returns the number of color changes along the unique path from $A$ to $B$.
• If your function exceeds 31 queries or provides malformed input, query will return -1.
• You must #include "colors.h"

Constraints

• $3 \le N \le 40\ 000$
• $1 \le X_i \ne Y_i \le N$ for each $1 \le i \le N - 1$
• The edges form a tree
• The hidden nodes $A$ and $B$ are distinct and have distance at least $2$

Scoring

Your program will be tested against several test cases grouped in subtasks.
In order to obtain the score of a subtask, your program needs to correctly solve all of its test cases.

Example

N = 7
edges = {
  {3, 4},
  {1, 6},
  {1, 5},
  {7, 2},
  {7, 3},
  {4, 1}
}

Suppose the following calls are made:

query({0, 0, 0, 0, 1, 1}) → 3
query({0, 1, 1, 0, 0, 0}) → 1
query({0, 1, 0, 0, 0, 0}) → 0

Then your function should return:

return {5, 7};

Explanation

• After the first query, the only possible pairs of hidden nodes are $(1, 2)$, $(5, 7)$ and $(6, 7)$, as the secret path has $3$ color changes.
• After the second query, only $(5, 7)$ and $(6, 7)$ are possible: $(1, 2)$ is excluded.
• After the third query, only $(5, 7)$ remains (the path between $6$ and $7$ has a color change).