Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

There is a weighted tree with n nodes and n-1 edges. The nodes are conveniently labeled…

  1. User

    There is a weighted tree with n nodes and n-1 edges. The nodes are conveniently labeled from 1 to n. The weights are positive integers at most 100. Define the distance between two nodes to be the sum of edges on the unique path between the nodes. You would like to find the diameter of the tree. Diameter is the maximum distance between a pair of nodes.

    Unfortunately, the tree isn't given to you, but you can ask some questions about it. In one question, you can specify two nonempty disjoint sets of nodes p and q, and the judge will return the maximum distance between a node in p and a node in q. In the words, maximum distance between x and y, where x ∈ p and y ∈ q. After asking not more than 9 questions, you must report the maximum distance between any pair of nodes.

    Interaction

    Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1 000). Description of the test cases follows.

    The first line of each test case contains an integer n (2 ≤ n ≤ 100) — the number of nodes in the tree.

    To ask a question, print "k_1\ k_2\ a_1\ a_2\ …\ a_{k_1}\ b_1\ b_2\ …\ b_{k_2}" (k_1, k_2 ≥ 1 and k_1+k_2 ≤ n). These two sets must be nonempty and disjoint. The judge will respond with a single integer max_{p,q} dist(a_p, b_q). If you ever get a result of -1 (because you printed an invalid query), exit immediately to avoid getting other verdicts.

    After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

    • fflush(stdout) or cout.flush() in C++;
    • System.out.flush() in Java;
    • flush(output) in Pascal;
    • stdout.flush() in Python;
    • see documentation for other languages.

    When you are ready to answer, print "-1\ d", where d is the maximum shortest distance over all pairs of nodes.

    You can only ask at most 9 questions per test case.

    Hack Format

    To hack, use the following format. Note that you can only hack with one test case.

    The first line should contain a single integer t (t=1).

    The second line should contain a single integer n (2 ≤ n ≤ 100).

    Each of the next n-1 lines should contain three integers a_i, b_i, c_i (1≤ a_i, b_i≤ n, 1 ≤ c_i ≤ 100). This denotes an undirected edge between nodes a_i and b_i with weight c_i. These edges must form a tree.

    Example Input

    2 5 9 6 10 9 10 2 99

    Output

    1 4 1 2 3 4 5 1 4 2 3 4 5 1 1 4 3 4 5 1 2 1 4 4 5 1 2 3 1 4 5 1 2 3 4 -1 10 1 1 1 2 -1 99

    Note

    In the first example, the first tree looks as follows:

    In the first question, we have p = {1}, and q = {2, 3, 4, 5}. The maximum distance between a node in p and a node in q is 9 (the distance between nodes 1 and 5).

    The second tree is a tree with two nodes with an edge with weight 99 between them.

  2. DeepSeek Assistant

    We need to devise a strategy to find the diameter of an unknown tree with up to n=100, edge weights up to 100, using at most 9 queries. In each query we can specify two non-empty disjoint sets p and q, and get the maximum distance between a node in p and a node in q.

    Goal: determine the maximum pairwise distance (diameter). We have up to 9 queries.

    We need to think about how to find the diameter without knowing the tree. Since we can query max distance between sets, we might try to find two nodes that are endpoints of a diameter.

    Standard approach for tree diameter: pick any node, find farthest node from it (say u), then find farthest from u, that is the diameter. But we cannot directly query distance to a single node; we can only ask about sets. But we can simulate that: ask max distance between a set containing a single node and the set of all other nodes? That's allowed: p={node}, q= all others, disjoint and nonempty. That would give the maximum distance from that node to any other node. So with one query we can find the farthest distance from a given node. But we need to identify which node is farthest, not just the max distance. We can try to binary search or use queries to locate the farthest node.

    But we have a limited number of queries (9). n ≤ 100, so maybe we can find the diameter by asking clever sets.

    We could try to find the two endpoints of the diameter via ternary search? But it's a tree; the distance function to a node is convex? Not sure.

    Alternatively, we could ask for maximum distance between all nodes? But we can't ask for all pairs directly. However, we can ask for the max distance between two sets covering the whole tree? But sets must be disjoint. If we partition nodes into two disjoint nonempty sets, we get the max distance across the partition. That might not be the diameter if the diameter endpoints lie in same set. But we can do multiple partitions.

    With 9 queries, maybe we can perform a "binary search" on the node set to find a farthest node from a starting node. Since n ≤ 100, we could ask queries that narrow down the candidate set.

    Let's think: Starting with node 1, we want to find the farthest node from 1. We can query: p={1}, q= rest (set R). The answer d1 = max_{v∈R} dist(1,v). This gives us the maximum distance but not which node(s) achieve it. We need to find a node that is at distance d1 from 1. Possibly we can find such a node by binary search on the set R, using queries that ask max distance from {1} to subsets of R. But note that if we query p={1}, q=S (subset of R), we get max distance from 1 to nodes in S. So we could try to find a subset that contains at least one farthest node. But we need to locate an actual node (like index) that is a farthest. Since n ≤ 100, we could ask a series of queries that test halves of the node set to see if the max distance is still d1, indicating that at least one farthest node lies in that half. This is like a "finding a maximum element by comparing to threshold". This is similar to finding a node with a property (distance = d1). We can do a binary search on the set of nodes. But we need to ensure that the farthest distance is exactly d1, and we want to locate one node achieving that.

    We can perform a procedure: maintain a candidate set C (initially all nodes except 1). While |C| > 1, split C into two roughly equal parts A and B. Query p={1}, q=A. If the answer equals d1, then there is at least one farthest node in A, so set C = A; else, then the farthest nodes must be in B (since d1 is max over entire R, and if A doesn't contain a node achieving d1, then B must contain all such nodes because d1 is the global maximum). Actually careful: If max_{v∈A} dist(1,v) < d1, that means no node in A achieves distance d1, but it could be that some node in B achieves d1. Since d1 is the maximum over whole R, and the max over A is less than d1, the maximum over B must be exactly d1 (since the overall max is d1, and if B's max were less than d1, then overall max would be less). But we need to be sure that B's max is d1. However, it's possible that both A and B have max less than d1 if we miscomputed d1? No, d1 is the max over all R, so at least one node in R achieves d1. If A's max < d1, then that node must be in B, so B's max = d1. So we can set C = B. So we can binary search down to a single node. How many queries does that take? Initial query to get d1: 1. Then we need to reduce from up to 99 nodes to 1 via binary splits. log2(99) ≈ 7. So worst-case about 7 additional queries, total 8. That is within 9. Then we have found a node u that is farthest from 1.

    Now we need to find the farthest node from u (the diameter). After we have u, we can similarly find the farthest node from u using the same method: query p={u}, q = all other nodes to get d2 = max distance from u. That would be the diameter. But wait, that would be the distance from u to its farthest node, which is the diameter because u is an endpoint of a diameter? Actually, if we start from an arbitrary node (1) and find a farthest node u, then u is guaranteed to be an endpoint of some diameter. Standard tree property: For any node x, any farthest node from x is an endpoint of a diameter. So yes, u is a diameter endpoint. Then the farthest node from u gives the diameter length. So we can just compute d2 as the maximum distance from u to any other node. But we need to be careful: To get d2 we could ask one query: p={u}, q = V \ {u}. That gives the max distance from u, which is the diameter. So we would be done. But we already used one query to get d1, and about 7 queries to locate u, total up to 8. Then we need one more query to get the diameter from u. That would be 9 total, which is exactly the limit. But we must ensure we don't exceed 9. In worst-case, 1 (d1) + ceil(log2(n-1)) (to locate u) + 1 (diameter) = 1 + 7 + 1 = 9 (since n-1 <= 99, log2(99) ≈ 6.6, ceil = 7). So 9 exactly. However, we need to be careful about the case where n=2: n-1=1, log2(1)=0, so we would need 1 (d1) + 0 + 1 = 2 queries. That's fine.

    But we need to consider that the binary search process might require splitting the set into two nonempty disjoint subsets each time. The candidate set C we maintain is a subset of nodes (excluding the start node). At each step, we split C into two nonempty parts. That's possible as long as |C| >= 2. If |C|=1, we stop. So binary splitting works.

    But there is nuance: After we get d1, we start with C = all nodes except 1. For each split, we need to query p={1}, q=A, where A is a nonempty proper subset of C? Actually, we can query with p={1} and q = A, where A is a subset of C. That's allowed because sets are disjoint (1 is not in A) and both nonempty. We need to be able to form A as a subset of C. That's fine.

    Now, after we locate u, we need to compute d2: ask p={u}, q = V \ {u}. That's a valid query. The answer is the diameter.

    Thus this approach seems straightforward and fits within 9 queries.

    But wait, we need to be careful about the number of queries used in the binary search: The worst-case number of splits needed to isolate a single element from N elements using binary splitting is ceil(log2(N)). Each split uses one query. However, note that when N is not a power of two, the splits may need to consider halves that are not exactly half but we can choose splits to minimize worst-case number of queries. The maximum number of queries needed to find a specific element among N when we can ask "is the element in set A?" and we know that the element is among the current set? Actually, we are using a decision process: we know the target value (d1) and we want to find a node achieving that distance. We ask: "Is there a node in A with distance = d1?" We can ask p={1}, q=A, and compare answer to d1. If answer == d1, then yes; else no. This is exactly a membership test for a set containing at least one farthest node. This is equivalent to finding one element among a set of candidates that satisfy a property, where we know at least one candidate satisfies it. The minimal worst-case number of yes/no questions to find one such element is ceil(log2(K)) if we can ask arbitrary subsets? Actually, it's like we need to locate one special element among N. With membership queries that can test any subset, we can binary search to locate one in ceil(log2(N)) questions. So that's fine.

    But there is a nuance: The answer we get is not a simple yes/no; it's the maximum distance from 1 to nodes in A. If that maximum equals d1, we know that A contains at least one node with distance d1. If it's less, we know A contains none. So it's indeed a membership test.

    Hence total queries: 1 (initial max from 1) + ceil(log2(n-1)) (binary search) + 1 (max from u) ≤ 1+7+1=9 for n≤100.

    Edge case: n=2: n-1=1, ceil(log2(1)) = 0? Actually, log2(1)=0, but we can't have a split because candidate set size 1. So we would skip binary search. Then queries: ask p={1}, q={2} -> get d1 (which is also diameter). But we also need to locate u: the farthest from 1 is node 2, so u=2. Then ask p={2}, q={1} to get diameter. That would be two queries. But we could simply output d1 after one query because we know it's the diameter? Actually, we need to be sure: Starting from node 1, the farthest node is 2, and the distance from that farthest node to any other (only node 1) is the same, so we could just output d1 without second query. But our algorithm as described would do two queries. But we can optimize: After we find u, we don't necessarily need to query again if we already know the diameter? If we have d1 from node 1, and we found that u is a farthest node, then the diameter is d1? Not necessarily. Consider a tree where the farthest node from 1 is u, but the diameter might be larger than d1? No, property: In a tree, the distance from any node to its farthest node is at least half the diameter, but not necessarily equal to the diameter. Actually, standard: For any node x, let y be a node farthest from x. Then y is an endpoint of some diameter. Proof: Consider any diameter endpoints a,b. For any node x, we have dist(a,b) ≤ dist(a,x) + dist(x,b). Also, for y farthest from x, we have dist(x,y) ≥ max(dist(x,a), dist(x,b)). But the property that y is an endpoint of a diameter is true: There exists a diameter such that y is one of its endpoints. So indeed, y is an endpoint of some diameter. Then the farthest distance from y (call it d2) is the diameter length. But is it always that d1 (the distance from x to y) equals d2? Not necessarily. Example: a path of 3 nodes with equal edge weights 1: 1-2-3. If x=2, farthest node is either 1 or 3, distance=1. But diameter is 2 (between 1 and3). So d1=1 not equal to diameter. So we do need to compute d2 from y. So for n=2, d1 is actually the diameter because there is only two nodes. But in general, after locating u from node 1, we cannot simply output d1. So we need the second query. For n=2, we could ask only one query, but our algorithm would ask two. But is that allowed? Since limit is 9, we can still ask two, it's fine. So we can keep the algorithm simple.

    But we must consider that we are allowed up to 9 queries. So worst-case 9 is fine.

    However, there is a potential issue: After we get d1 and binary search to find u, we may have used up to 1+ceil(log2(n-1)) queries. Then we query for d2. But note that we might have already obtained d2 implicitly? No.

    But we must also consider that we need to output the answer after at most 9 queries. So if n is large like 100, we may need exactly 9 queries. That's okay.

    But we need to verify that the binary search process indeed yields a node u that is farthest from node 1. The process ensures that after each step, we maintain a subset C that contains at least one node achieving distance d1 (the maximum from 1). Starting with C = all others, we know it contains at least one such node. Then we split C into A and B, both nonempty as long as |C|>=2. We query with A. If answer == d1, then there is a farthest node in A, so set C = A. Else answer < d1, then there is no farthest node in A, so farthest nodes must be in B, so set C = B. This works. At the end, C contains exactly one node, which must be a farthest node. Good.

    But we need to ensure that the query answer is exactly d1 (the max from 1 to all others). However, d1 is the maximum distance from node 1 to any other node. When we query A, we compute max distance from 1 to nodes in A. Since the overall max is d1, if A contains a node achieving d1, then max over A = d1. If A does not contain such a node, then max over A < d1. So the comparison works.

    One more nuance: The distance weights are integers, but d1 might be large (max sum up to 99*100=9900). The judge returns integer. No issue.

    Now, complexity: t up to 1000, but each test case we do up to 9 queries, total queries up to 9000, acceptable.

    But we need to handle multiple test cases sequentially, flush after each query.

    Implementation plan:

    For each test case:

    • Read n.
    • If n==2? We'll handle generally.

    Step 1: Find max distance from node 1: query p={1}, q = [2..n] (list of nodes 2..n). Read answer d1.

    • Keep d1.

    Step 2: Find a node u (farthest from 1) via binary search. candidate set C = [2..n] (list of ints) while size(C) > 1: split C into two roughly equal parts: first half A = first half (size floor(|C|/2) or ceil?), and B = the rest. Ensure A and B are nonempty. query: p={1}, q=A (list of nodes in A). Get ans. if ans == d1: C = A else: C = B u = C[0]

    Step 3: Find max distance from u: query p={u}, q = all other nodes (list of all nodes except u). Read answer diam.

    Step 4: Output "-1 diam" (format: "-1 d").

    But careful: In step 1, we ask a query with p size=1, q size = n-1, which is allowed since k1+k2 = n. Good.

    In step 2, when we split C, we must ensure that sets are nonempty and disjoint. p={1} is disjoint from q=A because 1 is not in A (since C originally excludes 1 and we maintain that). Good.

    Now about splitting: We should split the list into two nonempty subsets. For even sized C, we can split into halves. For odd, we can have one part with floor(|C|/2) and the other with ceil. Which part to use as A? We can use the smaller as A? But either is fine; we just need to decide consistently. Typically, we query with A being the first half (size floor(|C|/2)). This ensures both parts nonempty when |C|>=2.

    But need to be careful: When we query p={1}, q=A, if ans == d1, we set C = A; else C = B. So the size of C reduces at least by a factor of about 2 each time. The worst-case number of iterations is ceil(log2(initial size)). For size 99, we may need up to 7 splits: sizes: 99 -> 50? Actually, if we take A as floor(99/2)=49, B=50. If ans==d1, new size=49; else size=50. Next split 50->25 and 25 (or 25/25? Actually floor(50/2)=25, B=25) so both 25, then 13/12, etc. So number of splits: 99->50/49->25/25->13/12->7/6->4/3->2/1? Let's count: Starting size: 99 After 1: max 50 After 2: max 25 After 3: max 13 (ceil(25/2)? Actually from 25, floor(25/2)=12, B=13, worst-case B=13) After 4: max 7 (from 13: floor(13/2)=6, B=7) After 5: max 4 (from 7: floor(7/2)=3, B=4) After 6: max 2 (from 4: floor(4/2)=2, B=2? Actually split 4: A=2, B=2; worst-case can be 2) After 7: max 1 (from 2: split into 1 and 1, done). So 7 splits. Good.

    Thus total queries = 1 (initial) + 7 (splits) + 1 (final) = 9.

    But we need to verify that the initial query is necessary: Could we skip it and compute d1 as we go? For binary search, we need d1 as a reference. We could get d1 implicitly by performing queries that help us find a farthest node without knowing the maximum value a priori? Possibly we could do a "find max" by binary search on value, but that seems more complicated. So initial query is needed.

    Alternative: We could first find the diameter endpoints directly by some other method, but this approach is fine.

    We should also consider that we might be able to reduce one query by using the fact that after binary search we might already know the distance from 1 to u is d1, and maybe we could also compute the diameter as the maximum distance from u? But we need to query that because we don't know distances to other nodes. So we need the second query.

    But maybe we could combine: after binary search, we have u. Could we deduce the diameter from previous queries? Possibly not.

    Thus the algorithm seems sound.

    Now we must implement interaction. Important: After each query, we read an integer from input. The judge provides the answer. We must flush after printing.

    The output format for query: first k1, then k2, then the list of a_i (size k1), then list of b_i (size k2). In our case, when we ask p={1}, q=A, we have k1=1, k2=|A|, then the node 1, then the nodes in A in any order. For the final query p={u}, q = all others, k1=1, k2=n-1, list u then others.

    We need to print the query as a single line with numbers separated by spaces. Then flush, then read integer.

    But note: The example shows they printed "1 4 1 2 3 4 5" etc. In that example, they used k1=1, k2=4, then a1=1, then b1..b4=2,3,4,5. So order: k1, k2, a's, b's.

    Also note: The sets must be nonempty and disjoint. Our sets are {1} and A, and 1 is not in A by construction (since A ⊆ C ⊆ [2..n]), so they are disjoint.

    Now, we must handle the case n=2: candidate set C = [2] size 1, so skip binary search. Then we do initial query: p={1}, q={2} -> d1. Then we set u = 2 (since only candidate). Then final query: p={2}, q={1} -> diam. That's two queries. Works.

    But could we do better for n=2? Actually we could just do one query and output that as diameter, but it's fine.

    But what if n=3? candidate set size 2. After initial query d1. Then binary search: split C into two subsets of size 1 each. Query p={1}, q=A (one of them). If ans == d1, then u = that node; else u = the other. That's one split query. Then final query from u. Total queries = 1+1+1=3. That's within 9. Works.

    Now, verify property: After finding u, we query to get max distance from u. That should be the diameter.

    But is it always the diameter? Standard tree property: If u is a farthest node from some arbitrary node (1), then u is an endpoint of a diameter. Then the farthest node from u (call it v) yields the diameter length. So yes.

    Thus algorithm correct.

    But wait: Could there be multiple farthest nodes from 1? Our binary search will find one of them. That's fine; any one is an endpoint of some diameter.

    Edge Cases: We must ensure that when we split C, we always use a nonempty subset A that is a proper subset of C? Actually, we need A and B both nonempty. So we must ensure that when |C|>=2, we split into two nonempty subsets. Our splitting method should guarantee that.

    Implementation details:

    • Use list/vector for candidate nodes.
    • For each test case, after reading n, we will have to perform queries.

    Pseudo:

    int t; cin>>t; while(t--){ int n; cin>>n; vector all(n); iota... // step1: find d1 vector p1 = {1}; vector q1; for(int i=2;i<=n;++i) q1.push_back(i); int d1 = query(p1, q1); // function prints and reads. // binary search to find u vector candidates = q1; // all nodes except 1 while(candidates.size() > 1){ // split into two parts int sz = candidates.size(); int mid = sz/2; // floor, size of A = mid, at least 1? For sz>=2, mid>=1 (since sz/2 for sz=2 is 1; for sz=3, mid=1). That's fine. vector A(candidates.begin(), candidates.begin()+mid); vector B(candidates.begin()+mid, candidates.end()); int ans = query(p1, A); // p1 is still {1} if(ans == d1){ candidates = A; } else { candidates = B; } } int u = candidates[0]; // step3: get diameter vector pu = {u}; vector qu; for(int i=1;i<=n;++i) if(i!=u) qu.push_back(i); int diam = query(pu, qu); // answer cout << "-1 " << diam << endl; flush? Actually after output answer we should flush maybe not required but good practice. }

    But note: For query function, we need to output k1, k2, then the elements of p, then elements of q. Since p may be a vector of size 1, q of size variable.

    Be careful: In step1, if n=2, q1 size = 1, okay.

    Now we must consider the possibility that the answer d1 from step1 might be used later and compared with ans from split queries. Since the distances are integers up to maybe 100*99=9900, equality comparison is safe.

    Now, we need to flush after each query. In C++, we can use cout.flush() or endl (which flushes). Using endl is convenient: cout << ... << endl; ensures flush. However, we need to output many numbers, we can use endl at end.

    Now, test with sample? The sample input is:

    2 5 9 6 10 9 10 2 99

    Wait, the sample interaction in the problem statement shows output and input interleaved. The input for the judge includes the responses to queries. So the input after reading t=2, then for first test case n=5, then the judge's responses to queries: 9, 6, 10, 9, 10. And then for second test case n=2, responses: 99? Actually sample output shows queries and answer lines, and sample input shows the judge's responses. So let's decode:

    First test case: n=5. The output shows 5 query lines (1 4 1 2 3 4 5; 1 4 2 3 4 5 1; 1 4 3 4 5 1 2; 1 4 4 5 1 2 3; 1 4 5 1 2 3 4) then -1 10. So they asked 5 queries, then answer. The input would contain n=5 and then the responses to those 5 queries: 9,6,10,9,10 (as shown in the sample input after the 5?). Let's look: In the sample input (the Input section) they show:

    2 5 9 6 10 9 10 2 99

    So after t=2, they provide the first test case: n=5, then the responses: 9,6,10,9,10 (5 numbers). Then second test case: n=2, then responses: 99 (1 number). That matches.

    But note: In the output they also did a query "1 1 1 2" for the second test case? Actually in the sample output, they show after the first answer, they have "1 1 1 2" query and then "-1 99". Let's see: The sample output lines:

    1 4 1 2 3 4 5 1 4 2 3 4 5 1 1 4 3 4 5 1 2 1 4 4 5 1 2 3 1 4 5 1 2 3 4 -1 10 1 1 1 2 -1 99

    So for second test case, they did a query "1 1 1 2" (i.e., p={1}, q={2}), got response 99 (as per input), then output "-1 99". So that matches our algorithm for n=2? Our algorithm would first query p={1}, q={2} -> d1=99, then candidates size 1 so u=2, then query p={2}, q={1} -> diam=99, then output "-1 99". But they only did one query before answer. So they must have not done the second query. How did they get the answer? Possibly they realized that for n=2, d1 is the diameter. So they output after first query. Our algorithm would do two queries. That's okay, as 2 <=9. But we might also optimize to avoid the extra query for n=2 by checking if n==2, just output d1 as diameter after one query. But it's not necessary.

    But wait, for n=2, after step1 we already have d1. If we just output d1 as answer, would it always be correct? Yes, because the only pair is (1,2), so d1 is the distance between 1 and 2, which is the diameter. So we can output without step3. That would save one query, but not required.

    For n=1? Not allowed (n>=2).

    So we can incorporate: if n==2, after first query, output "-1 d1". But step1 already asks a query; we could also not ask any query and just output something? But we need to know the distance; we must ask at least one query to get the weight. So we ask one query. That's fine.

    But in our algorithm for n=2, after step1 we have d1. Then we go to binary search; candidates size = 1, so we skip loop, set u = 2. Then we would ask final query. But we can skip the final query if we know that u is the other node and the distance from u to 1 is same as d1 (since only two nodes). Actually, for n=2, after finding u (the only other node), we could just set diam = d1, without another query. So we can implement that: after binary search, if n==2, diam = d1; else we do the final query. But even if we do the final query, it's okay. However, the limit is 9, and n=2 uses only 2 queries, still within limit. So we don't need to optimize.

    But there is a catch: In the binary search, we use p={1} for all split queries. That's fine.

    Now, we need to verify that we never exceed 9 queries. For n=100, we computed 9 queries. But what about n=99? That's still 1+7+1=9. For n=100, initial set size n-1=99, same. So maximum queries = 9. So it's okay.

    But wait, for n=100, n-1=99, we need 7 splits. That totals 1+7+1=9. Good.

    But what about n=101? Not allowed, max 100.

    So we are within limit.

    Now we must double-check the splitting logic: At each step, we query with p={1}, q=A. We compare ans to d1. However, there is a subtlety: d1 is the maximum distance from 1 to any other node, which we obtained from query with q = all others. But we must consider that when we later query with q = A, we might get a different answer due to rounding? No, distances are exact.

    But careful: When we get d1, it's the maximum over all nodes except 1. If there are multiple farthest nodes, d1 is that distance. When we ask about a subset A, the answer is max_{v in A} dist(1,v). This will be exactly d1 if A contains any farthest node; otherwise it's strictly less. Since distances are integers, equality is reliable.

    Thus the algorithm is correct.

    However, there is a nuance: The problem statement says: "In one question, you can specify two nonempty disjoint sets of nodes p and q, and the judge will return the maximum distance between a node in p and a node in q." So the distance is between any node in p and any node in q. In our queries we always set p as a single node (1 or u). So we get max distance from that node to any node in q.

    Yes.

    Now, but wait: In step 3, we ask p={u}, q = all other nodes. That's fine. But we could also reuse previous queries? No.

    One more nuance: The judge may respond with -1 if our query is invalid. We must ensure our queries are valid: p and q nonempty, disjoint, and k1+k2 ≤ n. Since we always use p size 1, q size at most n-1, so sum ≤ n, and they are disjoint because p contains node 1 (or u) and q does not contain that node. But we must ensure that when we query with p={1}, q=A, we have A not containing 1. Our candidate set never includes 1, so fine.

    In step 3, p={u}, q = all nodes except u, disjoint.

    Also we need to ensure that we don't exceed 9 queries. In our algorithm for n=100 we use exactly 9. But is it possible that we need an extra query due to the splitting process? Let's calculate precisely: The binary search reduces the size of candidates from N to 1. The number of queries needed in worst-case for this process is the number of times we need to split until size becomes 1, i.e., ceil(log2(N)). For N=99, ceil(log2(99)) = 7 because 2^6 = 64, 2^7 = 128. So 7 splits. So total = 1 initial + 7 splits + 1 final = 9. For N=100? N is always n-1. For n=100, N=99. For n=99, N=98, ceil(log2(98)) = 7 (since 2^6=64, 2^7=128). For n=64? N=63, ceil(log2(63)) = 6 (2^6=64). So worst-case number of splits is 7 for N from 65 to 127? But N max 99 so 7. So total 9.

    But what if we start with node 1 and N=1? Then we skip binary search. For N=1, we need 0 splits. So total 2 queries. So always ≤9.

    Thus it's okay.

    Now, one more thing: The problem says "after asking not more than 9 questions, you must report the maximum distance". That means we cannot ask more than 9. Our algorithm respects that.

    Now, we should also consider the possibility of saving a query by not doing the initial query but instead using binary search to both find d1 and u simultaneously. For instance, we could start with candidate set = all nodes. But we need a reference value d1. Perhaps we could find d1 as the maximum of some queries. But that would likely use more queries. So we stick with the simple.

    Now, test with sample: First test case: n=5. According to the sample, they used 5 queries, not 3. Their method is different. But our algorithm would use: initial query: p={1} q={2,3,4,5} -> d1=9? In sample, the first query response is 9. So d1=9. Then binary search: candidates = [2,3,4,5]. Split: say A = first half: [2,3]? (size 2) or maybe [2]? Let's simulate with our method: size=4, mid=2, A=[2,3], B=[4,5]. Query p={1} q={2,3} -> answer? In sample, they have a query "1 4 2 3 4 5 1"? That's different; they used many queries rotating sets. Their approach seems to be something else. But our method would use queries: after initial, we need to binary search. Possibly the split query answer would be? Let's see the sample responses: The responses given in order: 9,6,10,9,10. The first response 9 corresponds to query "1 4 1 2 3 4 5". The second response 6 corresponds to "1 4 2 3 4 5 1". That's a different type of query. So our algorithm would produce different queries. But that's fine as long as we correctly compute diameter. The sample output's final answer is 10. Our algorithm would compute: After initial d1=9, binary search to find u. Let's compute distances in that tree. The tree is described? Not fully but from responses we can infer. But our algorithm should find u as the farthest node from 1. Likely that is node 5? Actually, the distances: from query1: max distance from 1 to {2,3,4,5} is 9, so farthest from 1 is at distance 9. Which node gives 9? Possibly node 5 (distance 9). In sample, they later have a query "1 4 5 1 2 3 4" (the 5th query) with response 10. That's max distance from 5 to {1,2,3,4} is 10, so diameter =10. So u would be 5. Our binary search should identify u=5. Let's test: candidates [2,3,4,5]. First split A = first half: say [2,3] (if we take floor(4/2)=2). Query p={1} q={2,3}. Response? Unknown from sample, but we can guess: distances: from 1 to 2? unknown; from 1 to 3? unknown. But we need to see if max among {2,3} is 9 or less. If the farthest node is 5, then max among {2,3} is less than 9, so response <9. So we would set candidates = B = [4,5]. Next, size=2, split: A = first half [4] (mid=1), B=[5]. Query p={1} q={4}. If response equals 9? Possibly distance 1-4 might be something else. If 1-4 distance is less than 9, then response <9, so we set candidates = B = [5]. That's u=5. So we would need two binary queries after initial, total queries = 1+2+1=4. But our algorithm would use 4 queries? Actually for n=5, N=4, ceil(log2(4))=2 splits. So total = 1+2+1 =4. But the sample used 5 queries and then answer. So we are using less. That's okay because limit is 9. So our algorithm is more query-efficient than the sample's. Great.

    Thus we can implement.

    Now, potential pitfalls:

    • We need to ensure that when we split, both parts are nonempty. For size=2, mid=1 gives A size 1, B size 1. Good.
    • For size=3, mid=1 (floor(3/2)=1) gives A size 1, B size 2. Good.
    • For size=1, loop not entered.

    Edge Cases: Suppose there are multiple farthest nodes from 1. Our binary search will still narrow down to one. That's fine. The algorithm will pick one of them arbitrarily. That node is an endpoint of some diameter. Good.

    One subtlety: When we ask the final query from u to all others, we get the diameter. But what if the tree has multiple diameters? Still fine.

    Now, we must ensure that we don't accidentally ask more than 9 queries. For n=100, we computed 9 queries. But wait, we need to be careful about the initial query: it uses p={1}, q= all others. That's one query. Then binary search: for N=99, we need up to 7 queries. Then final query: one more. That's 9 total. So exactly 9. However, we must be cautious: In the binary search, we might sometimes be able to skip a query if we deduce something? But we need to guarantee worst-case. So it's okay.

    But is there any possibility that we need an extra query due to the way we split? For example, when we split, we query with p={1}, q=A. This consumes one query. In the worst-case, we reduce the candidate set size from N to at most ceil(N/2) after each query. So number of queries needed to reduce to 1 is ceil(log2(N)). For N=99, ceil(log2(99)) = 7. So yes.

    But there is nuance: The binary search process might need to consider that when the candidate set size becomes 2, we split into two singletons. Query with p={1}, q=A (size1). If answer == d1, then we know the farthest node is the one in A, else it's the other. So one more query reduces to 1. So for N=2, we need 1 query. So total queries for N=2: initial(1) + 1 split + final(1) = 3. For n=3, N=2, that's 3 queries. For n=3, log2(2)=1, so 1+1+1=3. That's okay.

    Now, check: For n=100, N=99, ceil(log2(99)) = 7. 1+7+1=9. Perfect.

    But what about n=101? Not allowed.

    So we are within limit.

    Now, we must consider that the problem statement says "not more than 9 questions per test case". So as long as we don't exceed 9, it's fine.

    Now, implement query function. We'll have to print the query and read the answer. Since t can be up to 1000, and total queries up to 9000, it's fine.

    Implementation details in C++:

    int ask(const vector<int>& p, const vector<int>& q) {
        int k1 = p.size(), k2 = q.size();
        cout << k1 << " " << k2;
        for (int x : p) cout << " " << x;
        for (int x : q) cout << " " << x;
        cout << endl;
        cout.flush();
        int res;
        cin >> res;
        if (res == -1) exit(0); // invalid query, should not happen
        return res;
    }
    

    But careful: We need to handle the case where we print the query and then read the answer. There may be multiple test cases, we need to flush after each output.

    Alternatively, use endl which flushes.

    Now, after we output the answer "-1 d", we must also flush? Possibly not needed but safe to do.

    Now, we need to be careful about indexing: nodes are 1-indexed.

    Now, we need to confirm that our queries never violate the condition that p and q are nonempty and disjoint, and k1+k2 ≤ n. For final query, p size=1, q size=n-1, sum=n. Good.

    Now, test with n=2: initial query: p={1}, q={2}. That's valid. d1. Candidates = {2} size1 => skip loop. u=2. final query: p={2}, q={1}. That's valid. So 2 queries. But could we do 1? We can skip final if n==2, but not required.

    Now, think about potential issues: When we split C, we might create A and B such that A is the part we query. But we need to ensure that p and q are disjoint: p={1}, q=A, and 1 not in A because A is subset of candidates (which excludes 1). So OK.

    One more nuance: The problem statement says "two nonempty disjoint sets of nodes p and q" and "k_1, k_2 ≥ 1 and k_1+k_2 ≤ n". Our queries satisfy that.

    Now, regarding output formatting: The example shows the query printed as "k_1 k_2 a_1 a_2 … a_{k_1} b_1 b_2 … b_{k_2}". So we must output k1, then k2, then list of a's (p), then list of b's (q). That's what we do.

    Now, confirm that we handle the case where after splitting, we might query with p={1} and q=A where A might be size 1. That's allowed.

    Now, we need to consider the possibility that d1 may be used in comparisons, but if we split and query with A and get ans, we compare ans == d1. However, due to integer equality, fine. But note: The distances could be up to around 100*99 = 9900, within int.

    Now, test with a random tree to ensure correctness.

    But before finalizing, let's reason if there is any hidden subtlety: The binary search process relies on the property that if the max over A is less than d1, then all farthest nodes are in B. That holds because d1 is the maximum over the whole set, and A and B partition C. However, there is a nuance: We are using p={1} for all queries. But what if during binary search we use p={1} and q=A, but we have to ensure that 1 is not in A. Since we keep candidates as nodes other than 1, it's fine.

    Now, after we locate u, we query p={u} and q = all others to get the diameter. But is it possible that the farthest node from u is also 1? It could be, but the maximum over all others includes 1, so that's fine. The answer we get is the diameter.

    Now, verify the sample: Our algorithm for n=5 would produce:

    Step1: query p={1} q={2,3,4,5} -> get d1=9. Step2: candidates = [2,3,4,5]. Split mid=2 -> A=[2,3]. Query p={1} q={2,3} -> we need to guess the response from the hidden tree. In the sample tree, maybe distances: 1-2=?, 1-3=?. The sample didn't include such a query. But the sample tree: According to the description, the tree in the first example is shown (image not available). But we can infer from sample queries: They did queries rotating sets, but not this specific one. However, we can compute: They gave response for query p={2}, q={3,4,5,1} as 6. That's max distance from 2 to {1,3,4,5} is 6. Not directly helpful.

    But anyway, let's assume that for our algorithm, we would get some responses and eventually find u. Then final query from u (which is 5) would get 10 as diameter. So answer would be 10, matching sample.

    Thus algorithm works.

    Now, ensure we handle the case where d1 may be obtained from multiple nodes, and during binary search we might end up with a candidate that is not actually farthest? No, because we maintain invariant: the current candidate set always contains at least one node achieving distance d1. Initially it's all nodes other than 1, and there is at least one farthest. Then if we query A and ans == d1, then A contains at least one farthest, so set C = A. If ans < d1, then A contains no farthest, so B must contain all farthest nodes, so C = B. So at each step, invariant holds. At termination, C size 1, that node must be farthest. Good.

    Now, we need to consider if the query answer can be equal to d1 but A does not contain a farthest node? That would mean max_{v in A} dist(1,v) = d1 but no node in A has distance d1. That's impossible because if max = d1, there exists some node in A with distance exactly d1. So safe.

    Now, we must be careful about reading input. Since there are multiple test cases, we need to read responses after each query. Also, after we output the answer "-1 d", the judge will move to the next test case (if any). We should flush after answer as well.

    Now, we might want to optimize by not doing the final query if we have already asked about that pair? For example, if u turns out to be the node we already had in the initial query? Not needed.

    Now, we also need to consider the possibility that the tree is weighted, but we don't need to know weights.

    Now, there's a minor issue: In the binary search, we always query with p={1}. But what if the farthest node from 1 is 1 itself? Not possible because p and q are disjoint and q excludes 1. So farthest node from 1 is among other nodes.

    Now, we need to guarantee that the candidate set never becomes empty. Initially, n>=2, so candidate set size >=1. Good.

    Now, one more nuance: The binary search splitting must ensure that both A and B are nonempty. When |C| >= 2, we split with mid = floor(|C|/2). Since |C|>=2, mid is at least 1, and size - mid is at least 1. So both nonempty.

    Now, implement.

    But before coding, think about potential alternative approach: Could we find diameter with even fewer queries? Possibly, but not needed.

    Now, I want to double-check the worst-case query count for n=100. n-1=99, log2(99) ≈ 6.63, ceil=7. So total 9. That's exactly the limit. So we are safe.

    But wait: Could there be a scenario where we need to ask an additional query because the binary search might need to check both halves? No, we decide based on answer.

    Now, we need to implement the split in a way that guarantees at most 7 queries for n=100. But if we choose mid = ceil(|C|/2) instead of floor, the worst-case number of queries might also be 7. Actually, for N=99, splitting into 50 and 49: worst-case we might keep the larger half (50) then next split 25 and 25, then 13 and 12, then 7 and 6, then 4 and 3, then 2 and 2? Wait, let's compute: if we split with mid = ceil(N/2) = 50 (A size 50, B size 49). If farthest nodes are in B (size 49), then we go to B of size 49. Then we split 49: mid = ceil(49/2)=25, A size 25, B size 24. If farthest in B (size 24) then size 24; split: ceil(24/2)=12, A=12, B=12. Then maybe worst-case keep 12; split 12: ceil(12/2)=6, A=6, B=6; then 6: ceil(6/2)=3, A=3, B=3; then 3: ceil(3/2)=2, A=2, B=1; worst-case if we keep A of size2, then split 2: ceil(2/2)=1, A=1, B=1. That's 7 splits as well: sizes: 99->49->24->12->6->3->2->1? Actually count: 99 -> after first split (if go to B) size 49 (1), then size 49 -> after split maybe keep larger? If we split 49 into 25 and 24, worst-case keep 25? Actually we want worst-case number of queries, which is the maximum depth. For a given splitting strategy, the worst-case number of splits needed to reduce to 1 is the number of times you can halve the size, i.e., ceil(log2(N)). The exact way you split (floor vs ceil) doesn't change the worst-case number of splits because both produce halves of size at most ceil(N/2). The recurrence T(N) = 1 + T(ceil(N/2)) yields T(N) = ceil(log2(N)). For N=99, ceil(log2(99))=7. So it's fine.

    Thus our approach is robust.

    Now, we must be careful about the output format for answer: "-1 d". The problem statement says "print '-1 d'", where d is the maximum distance. So we output "-1" then space then d. And then newline.

    Now, consider potential pitfalls with reading/writing across multiple test cases. We need to flush after each query and also after answer.

    Now, we should also consider the possibility that the judge returns -1 if our query is invalid. If that happens, we should exit. We'll handle that.

    Now, think about the possibility of using node indices beyond n? No.

    Now, we can implement.

    But wait, is there any scenario where the binary search could get stuck? For example, if there are multiple farthest nodes, and we split in such a way that A contains some farthest nodes and B contains some farthest nodes, then whichever we choose we keep a set that contains at least one farthest node. That's fine.

    Now, verify with a small example: n=3, edges: 1-2 weight 5, 2-3 weight 5. So distances: d(1,2)=5, d(1,3)=10, d(2,3)=5. Diameter=10 between 1 and 3.

    Our algorithm: