Богатство, власть, сила — король пиратов Гол Д. Роджер достиг всего в этом мире. Слова, сказанные им перед смертью, отправили людей в море: «Мои сокровища? Если вы хотите, они ваши! Найдите их. Все, что у меня было, осталось в одном месте». В погоне за своими грёзами люди отправились на Гранд Лайн. Так началась Великая эпоха пиратов!

Это интерактивная задача.

На карте Гранд Лайн есть $$$n$$$ островов, соединённых $$$m$$$ возможными маршрутами. $$$i$$$-й маршрут позволяет переплыть с острова $$$a_i$$$ на остров $$$b_i$$$ за время $$$w_i$$$. Так, как погода и течения на Гранд Лайн непредсказуемы и постоянно меняются, иногда некоторые маршруты становятся недоступными. Вероятность доступности $$$i$$$-го маршрута оценивается как $$$p_i$$$.

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

Гарантируется, что для каждого острова $$$v$$$ существует маршрут из него на остров $$$u \gt v$$$ с вероятностью доступности $$$p_i = 100\%$$$. Таким образом, решение всегда существует вне зависимости от доступных маршрутов.

Чтобы случайная геренация маршрутов не влияла на оценку решения, для каждого списка возможных маршрутов вам нужно решить задачу для $$$q$$$ независимых случайно сгенерированных случаев.

Это задача с открытыми тестами

В этой задаче $$$10$$$ тестов. Входные данные для всех тестов доступны участнику и находятся в файлах input1.txt, input2.txt, ..., input10.txt.

В начале каждого хода программа жюри сообщит вам номера доступных маршрутов, исходящих из текущего острова, в формате $$$k$$$ $$$v_1$$$ $$$v_2$$$ $$$...$$$ $$$v_k$$$ ($$$1 \le k \le n$$$, $$$1 \le v_i \le m$$$) — количество маршрутов и их номера соответственно.

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

Если после перехода вместо значения $$$k$$$ вы получите целое число $$$0$$$, то это означает, что ваша программа сделала некорректный переход или превысила лимит в $$$2000$$$ переходов. Тогда ваша программа должна немедленно завершиться. В противном случае можно получить произвольный вердикт, поскольку решение будет продолжать считывать данные из закрытого потока.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Idleness limit exceeded. Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;

Если вы нарушили протокол взаимодействия или совершили более $$$2000$$$ переходов, вы получаете $$$0$$$ баллов за тест.

Иначе пусть суммарное время по всем запускам в вашем решении равно $$$s$$$. Если $$$s \lt s_{min}$$$, то вы получаете $$$10$$$ баллов за тест. Если $$$s \gt s_{max}$$$, то вы получаете $$$0$$$ баллов за тест. Иначе ваш балл равен $$$10 \cdot (\frac{s_{max} - s}{s_{max} - s_{min}})^2$$$.

Баллы за каждый тест округляются вверх до сотых и суммируются. Правила округления таковы, что, например, при округлении числа $$$10.112$$$ вверх до сотых получаем число $$$10.12$$$.