Это интерактивная задача.
Легендарное дерево покоится глубоко в лесу. Легенда гласит, что люди, которые узнают структуру этого дерева, навсегда станут легендарными гроссмейстерами.
Чтобы помочь вам определить дерево, богиня Микаэла рассказала вам, что это дерево состоит из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Она также позволила вам спросить что-то про дерево. Чтобы задать вопрос, вы должны назвать Микаэле два непересекающихся непустых множеств вершин $$$S$$$ и $$$T$$$ и произвольную вершину $$$v$$$. Затем Микаэла посчитает и скажет вам количество пар вершин $$$(s, t)$$$, где $$$s \in S$$$ и $$$t \in T$$$ таких, что простой путь от $$$s$$$ до $$$t$$$ содержит $$$v$$$.
Богиня Микаэла занята и сможет ответить вам только на $$$11\,111$$$ запросов.
Это ваш единственный шанс. Ваша задача — определить дерево и вывести его ребра.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 500$$$) — количество вершин в дереве.
Когда ваша программа определила дерево и готова вывести его ребра, выведите «ANSWER» на отдельной строке. Убедитесь, что все буквы являются заглавными.
Затем выведите $$$n-1$$$ строку, в каждой строке должны находиться два целых числа, разделенных пробелами, обозначающие вершины, которые являются концами фиксированного ребра. Каждое ребро должно быть выведено ровно один раз. Затем ваша программа должна немедленно завершиться.
Чтобы задать вопрос, действуйте следующим образом.
- Сначала выведите размер множества $$$S$$$ на отдельной строке. В следующей строке выведите $$$|S|$$$ различных целых чисел, разделенных пробелами, описывающих вершины $$$S$$$.
- Затем, аналогично, выведите размер множества $$$T$$$ на отдельной строке. В следующей строке выведите $$$|T|$$$ различных целых чисел, разделенных пробелами, описывающих вершины $$$T$$$.
- Затем, в последней строке, выведите $$$v$$$ — вершину, которую вы выбрали для этого запроса.
- Прочитайте ответ Микаэлы из входного файла.
Не забудьте, что $$$S$$$ и $$$T$$$ должны быть непустыми и непересекающимися.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Если ваша программа сделает слишком много запросов, задаст некорректный запрос или некорректно последует описанному выше протоколу взаимодействия, она может получить произвольный вердикт. В противном случае, ваша программа получит вердикт Неправильный ответ, если она выведет неправильное дерево.
Обратите внимание, что дерево загадано заранее и не зависит от ваших запросов.
Взломы
Взломы должны быть описаны следующим образом.
Первая строка должна содержать целое число $$$n$$$ ($$$2 \leq n \leq 500$$$) — количество вершин в дереве.
Следующие $$$n-1$$$ строк должны содержать по два целых числа $$$u$$$ и $$$v$$$, обозначающих наличие в дереве неориентированного ребра $$$(u, v)$$$ ($$$1 \leq u, v \leq n$$$).
5
5
3
1 2 3
2
4 5
2
ANSWER
1 2
2 3
3 4
2 5
В первом тестовом примере задано следующее дерево:
$$$n = 5$$$ задается программе. Затем программа задает Микаэеле запрос с $$$S = \{1, 2, 3\}$$$, $$$T = \{4, 5\}$$$, и $$$v = 2$$$, на который она отвечает $$$5$$$ (подходящие пары $$$(s, t)$$$ это $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, и $$$(3, 5)$$$).
