建议本题优先阅读 PDF 喵

PDF update: D.pdf

Description

本题是一个交互题。

有一个电学黑箱，它们由导线，二极管，灯泡组成，如果你因为准备 ICPC 导致了物理没有过关(但事实是，你不需要上大学物理)，我们简单介绍一下，本题不需要你有多高的物理水平。

你面前有一个电学黑箱，内部包含 $n$ 个灯泡（编号 $1\sim n$）。其内部电阻均为 $1 \Omega$。灯泡之间通过导线连接，这些灯泡和导线共同构成了一个树形结构（即：若将灯泡视作点，导线视作边，则 $n$ 个点之间由 $n-1$ 条边连接，且无环）。

特别的是，每条导线上可能嵌入了一个理想二极管。二极管具有单向导通性：

• 正向：电阻为 $0$。
• 反向：电阻为 $\infty$（视作断路）。

你可以使用欧姆表进行询问，格式为 $\texttt{? s t}$，该询问表示：将欧姆表的正极接在灯泡 $s$ 的触点上，负极接在灯泡 $t$ 的触点上。如果从 $s$ 到 $t$ 的路径上所有二极管均导通，返回路径上经过的灯泡数量（即电阻总和）。如果路径中存在反向二极管导致不导通，返回 $-1$。

例如如上图所示，如果你询问 $\texttt{? 1 2}$，那么其返回结果为 $2$，如果你询问 $\texttt{? 2 1}$ 路径中存在反向二极管导致不导通，返回 $-1$。

现在需要使用你手中的欧姆表，通过不超过 $2\times 10^4$ 次询问，还原黑箱内灯泡的连接关系（哪些灯泡相连）以及导线上二极管的方向（或是否存在二极管）。

Interaction

首先第一行交互器会输入一个整数 $n$ ($1 \leq n \leq 100$)，表示黑箱中灯泡的个数。

对于你的每一次询问，交互器会输出一个整数 $R$：

• 若 $R > 0$，表示从正极 $s$ 到负极 $t$ 导通，且路径上经过的灯泡总数为 $R$。
• 若 $R = -1$，表示该路径不导通。

你可以进行询问或提交答案。

询问格式：输出 $\texttt{? s t}$ ($1 \leq s, t \leq n$)，表示将欧姆表正极接在灯泡 $s$ 上，负极接在灯泡 $t$ 上。每次询问后请记得刷新缓冲区（flush）。

答案提交：如果你已经确定了黑箱结构，请按以下格式提交：

第一行输出一个符号 $\texttt{!}$。

接下来输出 $n$ 行，第 $i$ 行表示从灯泡 $i$ 出发，通过单根导线（可能含有正向二极管）直达的所有灯泡编号。具体要求如下：

• 第 $i$ 行输出若干个整数，表示所有满足 $i \to j$ 直接导通且中间无其他灯泡的编号 $j$。
• 每行内的编号需按从小到大排序。
• 如果灯泡 $i$ 没有指向任何其他灯泡，该行请输出 $\texttt{null}$。

Samples

请阅读本题 PDF 题面。

Note

根据上述样例，我们可以得到如下图的电路图，它满足所有询问，并且根据上述所有询问可以唯一确定如下的连接情况。

选手程序刷新输出缓冲后，通过管道连接它的测评程序（称为交互器）才能立刻接收到这些数据。

因为如果你输出了一些数据没有刷新缓冲区的话，这些数据可能被放置于内部缓存区里，而且或许没有被直接传输给 interactor。

为了避免这种情况的发生，你需要每次输出时用一种特殊的清除缓存操作。你可以使用如下语句来清空缓冲区：

• 对于 C/C++：$\texttt{fflush(stdout)}$；
• 对于 C++：$\texttt{std::cout << std::flush}$；
• 对于 Java：$\texttt{System.out.flush()}$；
• 对于 Python：$\texttt{stdout.flush()}$；

如果没有输出刷新缓冲区，你可能会遇到 Time-Limit 错误。