这是一个交互问题。
一棵传说中的树栖息在森林深处。传说,悟出这棵树的人将永远成为传奇宗师。
为了帮助您确定树,女神 Mikaela 向您透露,该树包含 $$$n$$$ 个顶点,从 $$$1$$$ 到 $$$n$$$ 枚举。她还允许您问她一些问题,如下所示。对于每个问题,您应该告诉 Mikaela 两个不相交的非空顶点集 $$$S$$$ 和 $$$T$$$,以及您喜欢的任何顶点 $$$v$$$。然后,Mikaela 将计算并给出顶点对 $$$(s, t)$$$ 的数量,其中 $$$s \in S$$$ 和 $$$t \in T$$$,这样从 $$$s$$$ 到 $$$t$$$ 的简单路径包含 $$$v$$$。
Mikaela 女神很忙,最多可以回答 $$$11\,111$$$ 问题。
这是你唯一的机会。您的任务是确定树并报告其边缘。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — 树中的顶点数。
互动
对于您想问的每个问题,请按以下方式互动。
1. 首先,在自己的行中打印 $$$S$$$ 的大小。在下面的行中,打印 $$$|S|$$$ 以空格分隔的不同整数,表示 $$$S$$$ 中的顶点。
2. 同样,在自己的行中打印 $$$T$$$ 的大小。在下面的行中,打印 $$$|T|$$$ 以空格分隔的不同整数,表示 $$$T$$$ 中的顶点。
3. 然后,在最后一行中,打印 $$$v$$$ — 您为此问题选择的顶点。
4. 从输入中读取 Mikaela 的答案。
请注意,$$$S$$$ 和 $$$T$$$ 必须不相交且非空。
打印查询后,不要忘记输出行尾并刷新输出。否则您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
如果您的程序提出太多问题、提出无效问题或未正确遵循上述交互指南,则可能会收到任意判决。否则,如果您的程序报告错误的树,它将收到错误答案的判决。
请注意,树是预先固定的,不依赖于您的查询。
黑客
Hacks 的格式应如下。
第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — 树中的顶点数。
以下 $$$n-1$$$ 行每行应包含两个空格分隔的整数 $$$u$$$ 和 $$$v$$$,表示存在无向边 $$$(u, v)$$$ ($$$1 \leq u, v \leq n$$$)。
输出
当程序实现树并准备好报告边缘时,在单独的行中打印“ANSWER”。确保所有字母均大写。
然后,打印 $$$n-1$$$ 行,每行包含两个空格分隔的整数,表示作为某条边的端点的顶点。每条边都应该准确报告一次。然后你的程序应该立即终止。
示例
输入 #1
5 5
输出 #1
3 1 2 3 2 4 5 2 ANSWER 1 2 2 3 3 4 2 5
注意
在示例中,树如下所示。
$$$n = 5$$$ 被赋予程序。然后程序向 Mikaela 提出一个问题,其中 $$$S = \{1, 2, 3\}$$$、$$$T = \{4, 5\}$$$ 和 $$$v = 2$$$,她用 $$$5$$$ 回答($$$(s, t)$$$ 对是 $$$(1, 4)$$$、$$$(1, 5)$$$, $$$(2, 4)$$$、$$$(2, 5)$$$ 和 $$$(3, 5)$$$)。