题目描述

这是一道交互题。

给定一棵 $n$ 点的树，树中有一条隐藏的链 $(u, v)$。

你可以向评测机提出若干次询问，每次询问格式应如 k x[1] x[2] ... x[k] 表示询问 $x[1],x[2],\dots,x[k]$ 这 $k$ 个点中有多少点在链 $(u, v)$ 上。

现在你需要找到这条链，保证 $u\neq v$。

注意：你询问的点不能重复。

输入格式

第一行一个整数 $n$。
接着 $n-1$ 行，每行两个整数 $u,v$ 表示 $u,v$ 之间存在一条边。

输出格式

每次询问，你需要向标准输出输出 $k+1$ 个数，格式见题面。
在你得出答案之后，你应该输出 ! x y，表示隐藏的链为 $(x,y)$，顺序不影响得分。

4
1 2
2 3
1 4

3

2

3 2 3 4

2 3 4

! 3 4

数据规模与约定

令 $lim$ 表示交互次数上限。

• $\texttt{subtask1(15pts): n <= 20, lim = 20 }$
• $\texttt{subtask2(10pts): n = 100, lim = 50}$
• $\texttt{subtask3(15pts): n = 1000, lim = 200}$
• $\texttt{subtask4(19pts): n = 100000, lim = 60}$，保证树是一条链。
• $\texttt{subtask5(11pts): n = 100000, lim = 60}$，保证树是菊花图。
• $\texttt{subtask6(30pts): n = 100000, lim = 60}$

程序模板：

#include <bits/stdc++.h> 
using namespace std;
int query(vector<int> &a) { // 传入你要询问的点，返回在链上的点的个数 
    printf("%d", (int)a.size());
    for (vector<int>::iterator v = a.begin(); v != a.end(); v++) printf(" %d", *v);
    putchar('\n');
    fflush(stdout);
    int d;
    scanf("%d", &d);
    return d;
}
int main() {
    vector<int> a(2);
	a[0]=1; a[1]=2;
    int w=query(a),x=-1,y=-1;
    if (w==2) x=1,y=2;
    printf("! %d %d\n", x, y);
    return 0;
}

$\texttt{idea: Lenstar, std: hydd, checker: Lenstar, data: Lenstar}$