「EZEC-8」猜树 加强版
题目背景
这是一道交互题。
题目描述
有一棵以 $1$ 为根的 $n$ 个点的有根树,您需要通过若干次询问得到这棵树的结构。
您可以使用两种询问:
1. `? 1 u v` 通过这种询问,您可以获得 $u$ 和 $v$ 之间的距离。
2. `? 2 u` 通过这种询问,您可以获得 $u$ 子树的大小和 $u$ 子树中的所有节点。
请通过使交互库输出不超过 $40000$ 个数,得到这棵树的结构。
### 交互方式
输入树的大小 $n$ 以开始交互。
交互过程中,您可以进行题目描述中的两种询问。
对于第一种询问,交互库将会返回一个非负整数,表示 $u$ 节点和 $v$ 节点间的距离。
对于第二种询问,交互库将会先返回一个正整数 $num$,表示 $u$ 子树的大小。接下来会在同一行中返回 $num$ 个正整数,表示 $u$ 子树中的所有节点(节点顺序会被打乱)。
在您确定答案后,请以 `! fa[2] fa[3] ... fa[n]` 的形式输出一行,停止交互。其中 $fa[i]$ 表示这棵树中 $i$ 号节点的父节点。
在您输出一行后,请清空缓冲区:
- 在 C++ 中,使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中,使用 `flush(output)`。
- 在 Python 中,使用 `stdout.flush()`。
- 其它语言请自行查阅文档。
输入输出格式
输入格式
见「交互方式」。
输出格式
见「交互方式」。
输入输出样例
输入样例 #1
5
1
5 1 5 2 4 3
3 4 2 5
1 3
输出样例 #1
? 1 1 2
? 2 1
? 2 2
? 2 3
! 1 1 2 2
说明
对于 $100\%$ 的数据:$2 \leq n \leq 5000$,$1\le u,v\le n$。