Legendary Tree

题意翻译

### 题目描述 这是一道交互题 有一个$n$个节点的树,你需要通过不超过$11111$次询问得知树的形态。 询问方式为给出两个非空**无交**点集$S\ T$和一个点$u$,可以得到满足$s \in S , t \in T$且路径$(s,t)$经过$u$点的二元组$(s,t)$的总数。 ### 交互方式 交互开始前输入一行一个正整数$n(2 \leq n \leq 500)$表示树的点数 交互时,每一组询问输出$5$行,第一行输出集合$S$的大小$|S|$,第二行输出$|S|$个正整数表示集合$S$;第三行输出$|T|$,第四行输出$|T|$个正整数表示集合$T$;第五行一个正整数$u$。 每一次询问输出完成后交互程序会向标准输入给出当前询问的答案。记得在每一次询问过后使用`fflush(stdout);`函数 如果你得到了树的形态,则第一行输出`ANSWER`,接下来$n-1$行每行输出一个两个正整数$u,v$表示一条树边。

题目描述

This is an interactive problem. A legendary tree rests deep in the forest. Legend has it that individuals who realize this tree would eternally become a Legendary Grandmaster. To help you determine the tree, Mikaela the Goddess has revealed to you that the tree contains $ n $ vertices, enumerated from $ 1 $ through $ n $ . She also allows you to ask her some questions as follows. For each question, you should tell Mikaela some two disjoint non-empty sets of vertices $ S $ and $ T $ , along with any vertex $ v $ that you like. Then, Mikaela will count and give you the number of pairs of vertices $ (s, t) $ where $ s \in S $ and $ t \in T $ such that the simple path from $ s $ to $ t $ contains $ v $ . Mikaela the Goddess is busy and will be available to answer at most $ 11\,111 $ questions. This is your only chance. Your task is to determine the tree and report its edges.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 2 \leq n \leq 500 $ ) — the number of vertices in the tree.

输出格式


When program has realized the tree and is ready to report the edges, print "ANSWER" in a separate line. Make sure that all letters are capitalized. Then, print $ n-1 $ lines, each containing two space-separated integers, denoting the vertices that are the endpoints of a certain edge. Each edge should be reported exactly once. Your program should then immediately terminate. Interaction For each question that you wish to ask, interact as follows. 1. First, print the size of $ S $ in its own line. In the following line, print $ |S| $ space-separated distinct integers, denoting the vertices in $ S $ . 2. Similarly, print the size of $ T $ in its own line. In the following line, print $ |T| $ space-separated distinct integers, denoting the vertices in $ T $ . 3. Then, in the final line, print $ v $ — the vertex that you choose for this question. 4. Read Mikaela's answer from input. Be reminded that $ S $ and $ T $ must be disjoint and non-empty. After printing a query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. If your program asks too many questions, asks an invalid question or does not correctly follow the interaction guideline above, it may receive an arbitrary verdict. Otherwise, your program will receive the Wrong Answer verdict if it reports an incorrect tree. Note that the tree is fixed beforehand and does not depend on your queries. Hacks Hacks should be formatted as follows. The first line should contain a single integer $ n $ ( $ 2 \leq n \leq 500 $ ) — the number of vertices in the tree. The following $ n-1 $ lines should each contain two space-separated integers $ u $ and $ v $ , denoting the existence of an undirected edge $ (u, v) $ ( $ 1 \leq u, v \leq n $ ).

输入输出样例

输入样例 #1

5
5

输出样例 #1

3
1 2 3
2
4 5
2
ANSWER
1 2
2 3
3 4
2 5

说明

In the sample, the tree is as follows. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1129E/3e95ead99a2c2448b4f1f57329ce10f7001f546b.png) $ n = 5 $ is given to the program. The program then asks Mikaela a question where $ S = \{1, 2, 3\} $ , $ T = \{4, 5\} $ , and $ v = 2 $ , to which she replies with $ 5 $ (the pairs $ (s, t) $ are $ (1, 4) $ , $ (1, 5) $ , $ (2, 4) $ , $ (2, 5) $ , and $ (3, 5) $ ).