Background

众所周知，竞赛生人与人之间的关系是一个稠密图。

知周所众，信竞生人与人之间的关系是一个完全图。

所知周众，数竞生人与人之间的关系是一个完全二部图。

众周所知，对某不知名 whk 大师 zcx 进行 $\cos$ 运算后得到 $1$。

Description

这是一道 IO 类交互题。详见 Notes 查看注意事项。

有一个 $n$ 个节点的竞赛图^[1]，但是你并不知道图中边具体方向的情况。

你需要在图上找出一条长度为 $n$、不经过重复点的路径。可以证明这样的链一定存在。答案可能不唯一，输出任意一个即可。

为了实现这个目标，你可以提出若干个问题。每次询问两个数字 $i,j$，表示查询两点之间的边的方向。

你最多可以提出 $10^4$ 个问题。

Constraints

• $n \leq 1000$

此外，还有一些子任务，其中的数据点满足特殊要求。

分值	$id =$	$n \leq$	特殊性质
$20\%$	$1$	$141$	无
$20\%$	$2$	$1000$	图是一张有向无环图
$20\%$	$3$		所有边的方向随机生成
$40\%$	$4$		无

---

Interaction

初始时，你需要从标准输入中得到 $id$ 和 $n$ 的值：

$\boxed{\begin{aligned} & id {\quad} n \end{aligned}}$

接下来，你可以提出若干个问题。每个问题按如下格式，输出到标准输出：

$\boxed{\begin{aligned} & \texttt? {\quad} i {\quad} j \end{aligned}}$

应满足 $1\leq i \leq n, 1\leq j \leq n, i \neq j$。

交互库将判断 $i$ 和 $j$ 之间连边的关系。

若是 $i$ 指向 $j$，交互库会返回 1。

$\boxed{\begin{aligned} & 1 \end{aligned}}$

若边 $j$ 指向 $i$，交互库会返回 0。

$\boxed{\begin{aligned} & 0 \end{aligned}}$

如果你的查询次数已经超过了 $10^4$ 次，交互库会返回 -1。你应该立即结束你的程序。这组测试数据记 $0$ 分。

$\boxed{\begin{aligned} & -1 \end{aligned}}$

如果你已经确定了答案，请按照以下的格式，按你找到的路径的顺序输出点的编号：

$\boxed{\begin{aligned} & \texttt{!} {\quad} a_1 {\quad} a_2 {\quad} \dots {\quad} a_n \end{aligned}}$

Notes

每次输出后，请立即输出换行符并刷新标准输出缓冲区。 否则可能得到 TLE 或 WA 的评测结果。

一般来说，如果你不会操作文件系统：

• 对于 C 语言，fflush(stdout) 可以刷新标准输出缓冲区（下文简称缓冲区），C++ 当然也可以使用这种方法。
• 对于 C++，可选的操作较多（以下内容默认你在 namespace std 下）：
  • 当你用 cout << endl 时，会输出换行符并立即刷新缓冲区；
  • 当你使用 cout << flush 时，会立即刷新缓冲区；
  • 当你使用 cout.flush() 时，也会立即刷新缓冲区。
• 对于 Java，可以使用输出流的 flush 函数，如 System.out.flush()。
• 对于 Python，可以使用 sys.stdout.flush()，或者在调用 print 时指定参数 flush=True。
• 对于 Pascal，可以使用 flush(output)。
• 对于 Rust，使用 io::stdout().flush()。

其他语言的使用者请自行查阅相关文档。

做出回答或接收到 $-1$ 后，请立即结束程序。否则，评测结果可能出现错误。

Sample Interaction

假设该组数据的图如下：

输入	输出	解释
1 4		输入该组测试点的子任务编号 $id$（该实例中为 $1$）和点数 $n=4$。
	? 1 2	你想知道点 $1$ 和点 $2$ 之间边的方向。
1		这条边从 $1$ 指向 $2$。
	? 4 2	你想知道点 $4$ 和点 $2$ 之间边的方向。
0		这条边从 $2$ 指向 $4$。
	! 3 1 2 4	你找到了一条链，为 $3\rightarrow1\rightarrow2\rightarrow4$。
		你已经做出了回答，并结束了程序运行。

---

1. 竞赛图是通过在无向完全图中为每个边分配方向而获得的有向图。 ↩︎