蚁群扩张 - 문제

这是一个交互式问题。

哥伦比亚大学的昆虫学系想要扩大其蚂蚁群落。

该群落目前由 $n$ 只雄蚁和 $n$ 只雌蚁组成，分别编号为 $1$ 到 $n$。科学家们想为每只雄蚁找到一只可以与之交配的雌蚁。由于蚂蚁是多夫制的，一只雌蚁可以同时与多只雄蚁交配。

两只蚂蚁只有在彼此吸引的情况下才能交配。一只雄蚁可能会被多只雌蚁吸引，反之亦然。

为了找出哪些蚂蚁对彼此吸引，科学家们可以在 Ant-ropic 开发的 AI（蚂蚁检测）工具的帮助下进行实验。在一次实验中，他们将 $x$ 只雄蚁和 $y$ 只雌蚁放入一个容器中。AI 会观察它们的行为，并报告一对彼此吸引的蚂蚁，或者报告不存在这样的蚂蚁。这次实验的成本是 $x + y$ 美元。

更正式地，你可以向交互器进行以下查询：

? x i_1 i_2 ... i_x y j_1 j_2 ... j_y —— 对雄蚁 $i_1, i_2, \dots, i_x$ 和雌蚁 $j_1, j_2, \dots, j_y$ 进行实验。交互器会回复某对彼此吸引的蚂蚁 i_k j_l，表示第 $i_k$ 只雄蚁可以与第 $j_l$ 只雌蚁交配；如果不存在这样的配对，则回复 -1 -1。在多次实验中可能会报告相同的配对。此查询的成本为 $x + y$ 美元。

在进行一些实验后，科学家们需要报告每只雄蚁可以与哪只雌蚁交配，如果不存在这样的雌蚁，则报告 $-1$。由于科学家们的预算有限，所有实验的总成本不能超过 $35\,000$ 美元。

输入唯一的一行包含一个整数 $n$ ($1 \le n \le 400$) —— 雄蚁和雌蚁群落的大小。

在读取这行输入后，交互将从你的第一次查询开始。

要进行查询，请按以下格式输出一行（不包含引号）：

? x i_1 i_2 ... i_x y j_1 j_2 ... j_y ($1 \le x, y \le n$, $1 \le i_1, i_2, \dots, i_x \le n$, $1 \le j_1, j_2, \dots, j_y \le n$)。

索引 $i_1, i_2, \dots, i_x$ 必须互不相同，对于 $j_1, j_2, \dots, j_y$ 也是如此。

在每次查询后，读取两个由空格分隔的整数 —— 查询的答案。如果存在彼此吸引的配对，答案将是某个 $k$ 和 $l$ ($1 \le k \le x$, $1 \le l \le y$) 的 i_k j_l，表示这对彼此吸引的蚂蚁。否则，答案将是 -1 -1。

此查询的成本为 $x + y$。

所有查询的总成本不能超过 $35\,000$。

问题的答案是一个序列 $p_1, p_2, \dots, p_n$，其中 $p_i$ 是第 $i$ 只雄蚁可以与之交配的雌蚁的编号，如果不存在这样的雌蚁，则为 $-1$。

一旦你确定了问题的答案，请按以下格式输出一行（不包含引号）：

如果有多个正确答案，输出其中任意一个即可。

在此之后，终止程序。

此任务中的交互器是非自适应的。换句话说，彼此吸引的蚂蚁对在整个交互过程中不会改变。

如果你进行的查询总成本超过 $35\,000$，你的程序必须立即终止，你将获得 Wrong Answer 评测结果。否则，你可能会获得任意评测结果，因为你的程序将继续从已关闭的流中读取。

在打印每一行后，不要忘记输出换行符并刷新输出缓冲区。否则，你将获得 Idleness Limit Exceeded 评测结果。要刷新缓冲区，请使用：

2
1 2
-1 -1

? 1 1 2 1 2
? 1 2 2 1 2
! 2 -1

在样例测试点中，雄蚁 $1$ 被两只雌蚁吸引，而雄蚁 $2$ 不被任何雌蚁吸引。在第一次查询中，AI 揭示了两种吸引关系中的一种。在第二次查询中，没有发现吸引关系。这些查询的总成本为 $6$。

QOJ.ac