#P7597. 「EZEC-8」猜树 加强版

「EZEC-8」猜树 加强版

题目背景

这是一道交互题。

题目描述

有一棵以 11 为根的 nn 个点的有根树,您需要通过若干次询问得到这棵树的结构。

您可以使用两种询问:

  1. ? 1 u v 通过这种询问,您可以获得 uuvv 之间的距离。
  2. ? 2 u 通过这种询问,您可以获得 uu 子树的大小和 uu 子树中的所有节点。

请通过使交互库输出不超过 4000040000 个数,得到这棵树的结构。

交互方式

输入树的大小 nn 以开始交互。

交互过程中,您可以进行题目描述中的两种询问。

对于第一种询问,交互库将会返回一个非负整数,表示 uu 节点和 vv 节点间的距离。

对于第二种询问,交互库将会先返回一个正整数 numnum,表示 uu 子树的大小。接下来会在同一行中返回 numnum 个正整数,表示 uu 子树中的所有节点(节点顺序会被打乱)。

在您确定答案后,请以 ! fa[2] fa[3] ... fa[n] 的形式输出一行,停止交互。其中 fa[i]fa[i] 表示这棵树中 ii 号节点的父节点。

在您输出一行后,请清空缓冲区:

  • 在 C++ 中,使用 fflush(stdout)cout.flush()
  • 在 Pascal 中,使用 flush(output)
  • 在 Python 中,使用 stdout.flush()
  • 其它语言请自行查阅文档。

输入格式

见「交互方式」。

输出格式

见「交互方式」。

5

1

5 1 5 2 4 3

3 4 2 5

1 3

? 1 1 2

? 2 1

? 2 2

? 2 3

! 1 1 2 2

提示

对于 100%100\% 的数据:2n50002 \leq n \leq 50001u,vn1\le u,v\le n