Во всех задачах этого контеста одинаковое условие, они отличаются только тестом. Подробнее об оценивании смотрите в разделе «Система оценки» в конце условия.

Задача является интерактивной.

Вы — опытный искатель сокровищ, вам в руки попала древняя карта, которая может вас обогатить. На карте отмечены лесные дороги, а на каждом перекрёстке этих дорог можно найти клад. Вы отправляетесь в путешествие в надежде отыскать все отмеченные на карте сокровища, но ещё не знаете, что вам противостоит злой волшебник, который хочет запутать дороги и не дать вам дойти до цели.

Карта сокровищ представлена в виде неориентированного графа, где вершины соответствуют перекресткам, а ребра — дорогам. Вы начинаете свой путь из некоторой фиксированной вершины, номер которой вам известен. Каждый раз, приходя в вершину, в которой вы не были ранее, вы выкапываете сундук с сокровищем и ставите в этой вершине флаг. В начальной вершине клад будет выкопан вами сразу же, а значит, и флаг будет установлен тоже сразу.

Находясь на перекрёстке, вы видите для каждой из соседних вершин её степень и есть ли там флаг. Кроме этого вам ничего не видно. К тому же, силы злого волшебника так велики, что он способен менять расположение дорог и перекрестков на местности без изменения структуры графа. Поэтому порядок дорог, выходящих из перекрестка $$$v$$$, может оказаться другим каждый раз, когда вы попадаете в перекресток $$$v$$$. Но не забывайте, что множество соседних перекрестков при этом не меняется, и про каждую выходящую из вершины $$$v$$$ дорогу вы знаете, выкопали ли вы уже клад ранее в ее втором конце.

Ваша задача — собрать сокровища из всех вершин графа как можно быстрее. Удачи в охоте!

На первой строке интерактор выведет целое число $$$t$$$ ($$$1 \leq t \leq 5$$$) — число карт, для которых вам нужно решить задачу.

Далее для каждой из $$$t$$$ карт интерактор сначала выводит описание графа, а потом начинает взаимодействие на этой карте. Сначала интерактор выведет описание графа и начальной вершины в следующем формате.

На первой строке содержатся четыре целых числа $$$n, m, start, base\_move\_count$$$ ($$$2 \leq n \leq 300$$$, $$$1 \leq m \leq min(\frac{n(n-1)}{2}, 25n)$$$, $$$1 \leq start \leq n$$$, $$$1000 \leq base\_move\_count \leq 30000$$$) — количество вершин и ребер в графе, номер вершины, в которой вы начинаете путешествие, и некоторое базовое число шагов, от которого зависит оценка за карту. Гарантируется, что у жюри есть решение, с высокой вероятностью обходящее карту за не более чем $$$base\_move\_count$$$ шагов.

Далее в $$$m$$$ строках даны описания ребер графа $$$u, v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$). Гарантируется, что граф связный, не содержит кратных ребер и степени всех вершин не превосходят 50.

Описание карт для каждого теста вы найдете в архиве 'map_descriptions.zip', который вы найдете в любом из архивов 'problem-X-materials.zip' в разделе «Материалы соревнования» — все они одинаковы.

Описание карт для каждого теста вы найдете в архиве map_descriptions.zip, приложенном к контесту.

После вывода описания графа начинается взаимодействие. Интерактор выводит описания вершин в следующем формате: $$$$$$R~d~deg_1~flag_1~deg_2~flag_2 \ldots deg_d~flag_d,$$$$$$ где $$$d$$$ — степень текущей вершины, $$$deg_i$$$ — степень $$$i$$$-й вершины, соседней с текущей, а $$$flag_i$$$ — индикатор того, есть ли в $$$i$$$-й вершине флаг (0 или 1). Порядок соседей в описании вершины каждый раз выбирается интерактором случайно равновероятно независимо. Помните, что вам не даны настоящие номера соседних вершин.

В ответ на описание вершины вы должны вывести одно целое число $$$i$$$ ($$$1 \leq i \leq d$$$), означающее, что вы выбрали вершину с описанием $$$deg_i~flag_i$$$. Не забывайте использовать операцию flush после каждого вывода. Если ваш вывод окажется некорректным, вы получите вердикт «Неправильный ответ».

Когда вы посетите все вершины графа хотя бы по одному разу, интерактор вместо описания вершины выведет строку «AC». Если вы не уложитесь в $$$2 \cdot base\_move\_count$$$ ходов, интерактор выведет строку «F». В обоих случаях после этого вы должны начать считывать описание следующей карты, либо, если это была последняя карта в тесте, ваша программа должна завершиться.

Ниже приведен пример взаимодействия интерактора и решения. Обратите внимание, что тест из примера не совпадает с тестом, на котором будет запускаться ваше решение.

Интерактор
Решение
1
3 3 1 1000
1 2
2 3
3 1
R 2 2 0 2 0
1
R 2 2 0 2 1
2
R 2 2 0 2 1
1
AC

Все задачи этого соревнования имеют одинаковые условия и отличаются только тестом. Каждая задача содержит один тест, описание карт которого доступно вам в архиве.

Каждый тест состоит из нескольких карт.

Оценкой решения за задачу будет $$$0$$$, если ваше решение для некоторой карты не смогло получить ответа «AC» или «F». Если решение корректно провзаимодействовало с интерактором на всех $$$t$$$ картах, оценка за задачу будет равна сумме оценок за каждую из карт.

Если вы успешно обошли граф из $$$n$$$ вершин, использовав $$$moves$$$ ходов, очки за карту рассчитываются так. Обозначим $$$$$$base\_fraction=\frac{base\_move\_count + 1}{n},$$$$$$ $$$$$$sol\_fraction=\frac{moves+1}{n},$$$$$$ $$$$$$c=\frac{90}{\sqrt{base\_fraction - 1}}.$$$$$$

Тогда:

• если $$$moves \leq base\_move\_count$$$, то за карту вы получите $$$100-c \sqrt{sol\_fraction - 1}$$$ очков.
• если $$$base\_move\_count < moves \leq 2 \cdot base\_move\_count$$$, то за карту вы получите $$$20 - \frac{10\cdot(moves + 1)}{base\_move\_count + 1}$$$ очков.

Для каждой задачи выбирается решение, набравшее наибольшее количество баллов за данную задачу. Обратите внимание, что максимум выбирается не для каждой карты в отдельности, а для всего решения целиком.

Итоговым результатом участника является сумма баллов по каждой из задач.