CF2245G NPC Challenge

This is an interactive problem. There is a hidden undirected tree consisting of $ n $ vertices. To find this tree, you may ask queries of the following form: - Pick a sequence of distinct vertices $ a_1, a_2, \ldots, a_k $ , where $ k \ge 1 $ . The interactor will process your sequence and return a subset of these vertices, denoted by $ S $ . The set $ S $ is generated by the following process: - Initially, $ S $ is an empty set. - The interactor processes the vertices in the exact order they appear in your sequence, from $ a_1 $ to $ a_k $ . - For each $ a_i $ , if $ a_i $ does not share an edge with any vertex that is currently in $ S $ , then $ a_i $ is added to $ S $ . Otherwise, $ a_i $ is ignored. - After processing all $ k $ vertices, the interactor returns the final set $ S $ to you. $ S $ is represented by a binary string $ s $ of length $ k $ , where $ s_i=\texttt{1} $ if and only if $ a_i \in S $ . Your task is to find all $ n-1 $ edges of the hidden tree. To make the problem harder, the sum of $ k $ over all queries must not exceed $ 30 \cdot n $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \le n \le 10^3 $ ), representing the number of vertices in the hidden tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^3 $ .

N/A

In the first test case, the hidden tree consists of $ n=2 $ vertices, and the only edge is $ (1,2) $ . - For the first query, $ a=[1,2] $ : - Vertex $ 1 $ is processed. Currently, $ S $ is empty. Since $ 1 $ has no neighbors in $ S $ , it is added to $ S $ . $ S $ becomes $ \{1\} $ . - Vertex $ 2 $ is processed. Its neighbor, vertex $ 1 $ , is already in $ S $ . Thus, vertex $ 2 $ is ignored. In the second test case, the hidden tree consists of $ n=5 $ vertices. The edges are $ (1, 2) $ , $ (2, 3) $ , $ (2, 4) $ , and $ (3, 5) $ . - For the first query, $ a=[1,2,5] $ : - Vertex $ 1 $ is processed. $ S $ is empty. It is added to $ S $ . $ S $ becomes $ \{1\} $ . - Vertex $ 2 $ is processed. It shares an edge with vertex $ 1 \in S $ . It is ignored. - Vertex $ 5 $ is processed. Its only neighbor is vertex $ 3 \notin S $ . It is added to $ S $ . $ S $ becomes $ \{1, 5\} $ . - For the second query, $ a=[5,3,4,2,1] $ : - Vertex $ 5 $ is processed. $ S $ is empty. It is added to $ S $ . $ S $ becomes $ \{5\} $ . - Vertex $ 3 $ is processed. It shares an edge with vertex $ 5 \in S $ . It is ignored. - Vertex $ 4 $ is processed. Its only neighbor is vertex $ 2 \notin S $ . It is added to $ S $ . $ S $ becomes $ \{4, 5\} $ . - Vertex $ 2 $ is processed. It shares an edge with vertex $ 4 \in S $ . It is ignored. - Vertex $ 1 $ is processed. Its only neighbor is vertex $ 2 \notin S $ . Since it has no neighbors in $ S $ , it is added to $ S $ .