NPC Challenge

This is still an interactive problem. The hack format describes the hidden tree supplied to the interactor; your program itself reads only $t$ and each $n$. Reading the next $n-1$ edges would be wonderfully convenient and completely wrong.

1. What a query really gives us

For a queried sequence, the returned 1 vertices form the greedy independent set obtained by processing that order.

Two immediate facts matter:

• The selected set is independent.
• Every rejected vertex has a neighbor that was selected earlier.

So a query partitions a set into a known independent set and the remaining vertices. That is already useful, but we need a more precise tool.

2. A neighborhood oracle for two independent sets

Let $A$ and $B$ be disjoint independent sets. Query the concatenation

$$A \mathbin{+} B.$$

Because $A$ is independent, every vertex of $A$ is selected. Now consider $b\in B$:

• vertices processed earlier inside $B$ cannot be adjacent to $b$, since $B$ is independent;
• therefore $b$ is rejected exactly when it has a neighbor in $A$.

Hence the zeroes in the $B$ part of the response are exactly

$$N(A)\cap B.$$

Call this operation touching(A, B). The slightly cursed detail is that the vertices we want are represented by zeroes, not ones.

3. Recovering all edges between two independent sets

We next solve this subproblem:

• $A$ and $B$ are independent;
• every vertex of $B$ has at least one neighbor in $A$;
• recover every edge between $A$ and $B$.

Let this routine be recoverCross(A, B).

Base case

If $|A|=1$, every vertex of $B$ must be adjacent to the sole vertex of $A$. We can report all those edges immediately, with no query.

Divide and conquer

Split $A$ into two nearly equal halves $A_L$ and $A_R$.

First compute

$$B_L=N(A_L)\cap B$$

using touching(A_L, B). These are exactly the candidates for the left recursive call.

What belongs to the right call?

• Every vertex in $B\setminus B_L$ has no neighbor in $A_L$. Since it has some neighbor in all of $A$, it must have a neighbor in $A_R$.
• A vertex in $B_L$ may neighbor both halves. Find those vertices with touching(A_R, B_L).

Therefore

$$B_R=(B\setminus B_L)\cup\bigl(N(A_R)\cap B_L\bigr).$$

Now recurse on $(A_L,B_L)$ and $(A_R,B_R)$.

The invariant is preserved: every candidate supplied to a child has a neighbor in that child's $A$ set. At singleton leaves, the invariant identifies every individual edge.

4. Recovering an arbitrary induced forest

Let build(U) recover every hidden edge whose endpoints both lie in $U$.

Query all of $U$. Let

• $I$ be the vertices whose bits are 1;
• $R$ be the vertices whose bits are 0.

The set $I$ is independent, so the edges of the forest induced by $U$ fall into only two categories:

1. edges with both endpoints in $R$;
2. edges between $I$ and $R$.

There are no edges inside $I$.

First call build(R). This recovers the entire forest induced by $R$.

We cannot directly use touching(R,I), because $R$ need not be independent. However, its now-known graph is a forest, so we can 2-color every connected component. Let the two global color classes be $C_0$ and $C_1$. Each class is independent, even across different components.

For each $C_j$:

1. Compute $B_j=N(C_j)\cap I$ using touching(C_j,I).
2. Call recoverCross(C_j,B_j).

Since $C_0\cup C_1=R$, this recovers every edge between $R$ and $I$. Together with the recursive result inside $R$, all edges in $U$ are now known.

The recursion terminates because the first queried vertex is always selected, so $R$ is strictly smaller than $U$.

5. Correctness proof

We prove by induction on $|U|$ that build(U) recovers exactly the edges induced by $U$.

For $|U|\le 1$, there are no edges.

For a larger $U$, its query produces $I$ and $R$.

• By induction, build(R) recovers exactly all $R$-$R$ edges.
• There are no $I$-$I$ edges because $I$ is independent.
• The recovered forest on $R$ is correctly 2-colored into independent sets $C_0,C_1$.
• touching(C_j,I) returns exactly the vertices of $I$ adjacent to $C_j$.
• recoverCross recovers exactly every edge between those two independent sets.

Thus every $I$-$R$ edge is recovered, no nonexistent edge is inserted, and all three possible endpoint categories are handled. The induction follows.

6. Why the query budget fits

The relevant cost is the sum of sequence lengths, not merely the number of queries.

Consider the chain of outer build calls. Give each vertex a layer equal to the call where it first enters the selected set $I$. If a vertex survives through $c-1$ earlier layers, then in each such layer it was rejected by a neighbor selected in that layer. These neighbors are distinct, and the corresponding tree edges can each be charged only once. Therefore

$$\sum_v (\operatorname{layer}(v)-1)\le n-1.$$

Consequently:

• all main build queries have total length at most $2n-1$;
• all two-color-class neighborhood queries have total length below $3n$.

For recoverCross, each split halves $A$, so there are at most

$$\lceil\log_2 n\rceil\le 10$$

split levels. At any fixed split level, an $A$ vertex occurs in one current block. If a $B$ vertex occurs in several blocks, every additional occurrence is forced by a different incident tree edge; the same charging handles the second overlap query. The cross-edge sets from different outer layers are edge-disjoint. Carrying this level-by-level charge through the exact two-query split, while noting that singleton blocks issue no query, gives less than $25n$ symbols for all cross-edge recovery calls.

Together with the less than $5n$ outer cost, the total is at most $30n$.

7. Implementation details

• Vertices are stored 0-indexed internally and printed 1-indexed.
• Every query uses endl, which flushes immediately.
• If the response is -1 or input closes, terminate at once.
• The recovered adjacency list is also what we use to 2-color the recursive forest.

The local running time is $O(n\log n)$ apart from tiny vector-management constants, and the interaction uses at most $30n$ queried vertices.