题目描述

「Codeforces Round #564 赛前四天撞题 D」

这是一道交互题。

Nauuo 是一个喜欢二叉树的女孩子。

这天，她创造了一个有 $n$ 个节点的二叉树。节点的编号从 $1$ 到 $n$，其中 $1$ 是二叉树的根节点。

不过，她不记得这棵二叉树具体长什么样子了，她只记录了二叉树上任意两个节点之间的距离。你可以通过向她询问有关距离的信息来还原这棵二叉树，两个节点之间的距离定义为它们之间最短路上的边数。

你可以向 Nauuo 询问不超过 $30000$ 次有关距离的信息。你只需要告诉她 $2\sim n$ 号节点的父亲的编号就可以了。

交互方式

最开始，交互器会向标准输入中输入一个正整数 $n$。

接下来，你可以通过标准输出向交互器询问两个节点之间的距离。

对于一次询问，你需要输出一行 ? u v 表示你想让 Nauuo 告诉你节点 $u$ 和节点 $v$ 在这棵二叉树上距离，然后换行并刷新缓存。

在每次询问后，交互器会向标准输入中输入一个非负整数 $d$，表示节点 $u$ 和节点 $v$ 之间的距离。

当你的所有询问结束后，你需要输出一行 ! p，$p$ 是一个长为 $n-1$ 的正整数序列，第 $i$ 个数表示第 $i+1$ 个节点在这棵二叉树上的父亲，然后换行并刷新缓存。

当你的程序正确时，保证交互器使用的时间不会超过 $500\ \text{ms}$。

如果你的询问次数超过 $30000$ 次，那么评测机将会返回 Wrong Answer 或 Time Limit Exceeded，你的程序将会获得 $0$ 分。

如果你的程序没有及时刷新缓存，那么评测机将会返回 Time Limit Exceeded，你的程序将会获得 $0$ 分。

如果你的程序使用 C++，可以使用 fflush(stdout) 或 cout.flush() 或 cout << endl 来刷新缓存；

如果你的程序使用 Java，可以使用 System.out.flush() 来刷新缓存；

如果你的程序使用 Pascal，可以使用 flush(output) 来刷新缓存；

如果你的程序使用 Python，可以使用 stdout.flush() 来刷新缓存。

样例 1

4
1
2
3

? 1 2
? 1 3
? 3 4
! 1 2 1

样例 1 的二叉树形态如下。

在第一次询问中，$1$ 号节点和 $2$ 号节点之间的距离是 $1$（$1\to 2$）。

在第二次询问中，$1$ 号节点和 $3$ 号节点之间的距离是 $2$（$1\to 2\to 3$）。

在第三次询问中，$3$ 号节点和 $4$ 号节点之间的距离是 $3$（$3\to 2\to 1\to 4$）。

5
4
1

? 4 3
? 2 4
! 1 5 2 1

样例 2 的二叉树形态如下。

数据范围与提示

对于全部的数据，$2\le n\le 3000$。

你输出的 $u,v$ 应该满足 $1\le u,v\le n$，$p_i$ 应该满足 $1\le p_i\le n$，否则评测机会返回 Wrong Answer。

保证交互器输出的 $d$ 满足 $0\le d\le n-1$。

为什么要开 6s ？