Зельда опять бродит по подземельям, и ей очень хочется победить всех боссов, которые в них прячутся. Однако не всех боссов Зельда способна победить сразу, поэтому она тщательно выбирает, с кем ей сразиться сначала.

Иерархия боссов представляет собой подвешенное дерево, где вершины — это боссы, а рёбра — отношения начальник/подчиненный между боссами. Если в дереве вершина $$$v$$$ является ребенком вершины $$$u$$$, то босс с номером $$$u$$$ — непосредственный начальник босса с номером $$$v$$$. Будем называть непосредственного начальника лордом, а непосредственного подчиненного — слугой.

Зельда придерживается следующей стратегии:

1. Она выбирает таких $$$u$$$ и $$$v$$$, что $$$v$$$ — единственный слуга босса $$$u$$$.
2. Затем она расправляется с боссом $$$v$$$.
3. После этого все слуги босса $$$v$$$ переходят в подчинение $$$u$$$.
4. Процесс повторяется.

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

1. Выбирается босс $$$w$$$ с самым большим числом слуг (если таких несколько, то имеющий максимальный номер из них).
2. Выбирается его слуга $$$y$$$ с наибольшим номером.
3. $$$y$$$ становится лордом всех остальных слуг $$$w$$$.
4. $$$y$$$ при этом остается слугой $$$w$$$.

После этого Зельда снова ищет боссов, у которых ровно один подчиненный, и побеждает их, затем иерархия боссов снова перестраивается, и так до тех пор, пока Зельда может найти, кого ей победить. Помогите Зельде понять, сколько боссов останется после всех ее побед.

Принцесса Зельда готовится сражаться с Нуллом и оптимизирует работу Жезла Трифа: она настроила жезл так, что теперь он может вызывать пару эхо одним заклинанием.

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

Всего у Зельды есть $$$n$$$ эхо, $$$i$$$-e из которых имеет имя $$$s_i$$$, и $$$m$$$ волшебных слов заклинаний, $$$i$$$-e из которых равно $$$t_i$$$. Формально правила следующие: пару эхо $$$i$$$ и $$$j$$$ можно вызвать заклинанием номер $$$k$$$, если

• $$$t_k$$$ является префиксом $$$s_i$$$;
• $$$t_k$$$ является префиксом $$$s_j$$$;
• не существует строки длиннее, чем $$$t_k$$$, которая также является и префиксом $$$s_i$$$, и префиксом $$$s_j$$$.

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

В глубинах Застывшего Мира, где неподвижно даже время, скрывается Линк. Силы тьмы похитили его, и только Зельда, храбрая принцесса Хайрула, может спасти его.

Зельда обладает древним артефактом — Жезлом Трифа, который при активации загорается огнем, если герой Линк находится на расстоянии не больше $$$2d$$$ от жезла. Правда, Зельда читала инструкцию по использованию Жезла очень давно и уже забыла, чему равно $$$d$$$, она только помнит, что $$$d$$$ целое и лежит в отрезке от $$$1$$$ до $$$10^5$$$.

Сейчас Зельда находится в точке $$$(0, 0)$$$ и знает, что Линк находится на расстоянии не больше $$$d$$$ от нее, то есть если активировать жезл, то он загорится.

Линк спрятан силами тьмы в некоторой точке $$$(x_0, y_0)$$$ с необязательно целыми координатами, причем $$$-10^5 \le x_0, y_0 \le 10^5$$$. Зельда хочет как можно быстрее найти его. Для этого она может не более $$$400$$$ раз перейти в произвольную точку $$$(x, y)$$$ ($$$-10^6 \le x, y \le 10^6$$$) координатной плоскости и активировать Жезл, чтобы проверить, находится ли Линк на расстоянии не больше $$$2d$$$.

Помогите Зельде найти координаты Линка с абсолютной погрешностью каждой из координат точки не более $$$10^{-3}$$$.

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

Взаимодействие с интерактором проходит в виде запросов со стороны вашей программы и ответов со стороны интерактора. Каждый запрос представляется в виде «? $$$x$$$ $$$y$$$», что означает перейти в точку с вещественными координатами $$$x$$$ и $$$y$$$ ($$$-10^6 \le x, y \le 10^6$$$) и активировать Жезл Трифа. В качестве ответа на запрос вы получите одну из двух строк:

• «YES», если Линк находится на расстоянии не больше $$$2d$$$ от точки с координатами $$$(x, y)$$$;
• «NO» в противном случае.

Чтобы вывести ответ на задачу, напечатайте «! $$$x_0$$$ $$$y_0$$$», где $$$x_0$$$ и $$$y_0$$$ — предполагаемые координаты места, где спрятан Линк. Этот вывод не учитывается в количестве запросов.

Если в какой-то момент ваша программа превышает лимит в $$$400$$$ запросов или вы выводите запрос в точке за пределами доступной области, интерактор завершится с вердиктом WA (Wrong Answer).

Не забывайте после каждого запроса выводить символ перевода строки ('{\}n') и сбрасывать буфер вывода, чтобы интерактор получил ваш запрос. Это можно сделать с помощью std::cout.flush() в C++, System.out.flush() в Java и sys.stdout.flush() в Python, а также аналогичными командами в других языках. Если ваша программа не сбрасывает буфер вывода, она получит вердикт TL (Time Limit Exceeded) или IL (Idleness Limit Exceeded).

После долгих путешествий и приключений по Хайрулу Линк и Зельда решили отдохнуть и отвлечься от боев с монстрами и спасения королевства. Линк предложил Зельде сыграть в интересную числовую игру, которую он сам недавно узнал.

Правила игры довольно просты: есть два целых положительных числа $$$A$$$ и $$$B$$$ и число $$$k$$$. Игроки ходят по очереди, начинает Зельда. За ход игрок может сделать ровно одно из двух действий:

• Вычесть целое число от $$$1$$$ до $$$k$$$ из числа $$$A$$$;
• Прибавить целое число от $$$1$$$ до $$$k$$$ к числу $$$B$$$.

При этом, в процессе игры числа $$$A$$$ и $$$B$$$ должны оставаться положительными; если же игрок сделал такой ход, что одно из чисел перестало быть положительным, он проигрывает. Выигрывает же в игре тот, после чьего хода сумма чисел $$$A$$$ и $$$B$$$ стала простым числом.

Зельда хочет показать, что не уступает Линку в остроумии. Подскажите ей, может ли она выиграть в игре вне зависимости от игры соперника?

Поверхность мира Хайрул усеяна холмами и ущельями, полными опасностей.

Зельда ориентируется по карте Хайрула, на которой отмечено $$$n$$$ локаций. Каждая локация имеет свою высоту над уровнем моря $$$a_i$$$.

Холм — это подпоследовательность локаций (не обязательно идущих подряд, но имеющих возрастающие номера), высоты которых сначала строго возрастают, а затем строго убывают. Иными словами, последовательность $$$i_1, \ldots, i_k$$$ называется холмом, если $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$ и есть некоторое $$$j$$$ от $$$1$$$ до $$$k$$$, что $$$a_{i_1} \lt a_{i_2} \lt \ldots \lt a_{i_j}$$$ и $$$a_{i_j} \gt a_{i_{j+1}} \gt \ldots \gt a_{i_k}$$$. Обратите внимание, что холм может состоять даже из одной локации.

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

Поскольку холмов может быть очень много, Зельде достаточно найти остаток от деления количества холмов на $$$10^9 + 7$$$. Помогите принцессе справиться с этой задачей.

A nameless country consists of $$$n$$$ cities connected by $$$m$$$ bidirectional roads, such that it is possible to reach any city from any other.

There are three factions controlling this country: $$$i$$$-th faction occupies some connected set of cities $$$\{a_{i,j}\}$$$. That is, if we leave only the cities controlled by a specific faction, along with the roads between them, there will be a path between any two of them. It is also known that no city is controlled by more than one faction, meaning $$$a_{i,p} \neq a_{j,q}$$$ for $$$i \neq j$$$.

To celebrate the Equinox you need to mark some cities as main tourist attractions for the celebration. For all the factions so be satisfied, these cities along with factions' cities should form a connected set. Formally, it is necessary to choose a set of cities $$$B$$$ such that any two cities from the set $$$S = B \cup \{a_{i,j}\}$$$ are connected by a path that passes only through cities from $$$S$$$.

Of course, the most obvious way is to mark all the cities in the country, but the government will not be satisfied with such a solution. Find a suitable set $$$B$$$ of minimal size.

Зельда нашла Линка (ура!), но теперь ей нужно сварить лечебный смузи, чтобы нейтрализовать влияние черной магии и поправить здоровье друга.

Приготовление смузи — это огромный квест, перед началом которого Зельда выбирает $$$n$$$ ингредиентов, заданных числами от $$$0$$$ до $$$10^9$$$, и упорядочивает их в последовательность $$$a_i$$$. Разрешается брать повторяющиеся ингредиенты, то есть $$$a_i = a_j$$$.

Затем принцессе необходимо найти секретный ингредиент, номер которого вычисляется следующим образом:

1. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ для последовательности $$$a_1, \ldots, a_{i-1}, a_i$$$ определяется $$$b_i$$$ — минимальный номер ингредиента, которого в этой последовательности нет (обозначается как $$$\mathrm{mex}(a_1, \ldots, a_i)$$$). Например, $$$\mathrm{mex}(1, 7, 2, 2, 0, 5, 4) = 3$$$ и $$$\mathrm{mex}(1, 4, 5, 2, 3) = 0$$$.
2. От полученной последовательности $$$b_1, \ldots, b_n$$$ также вычисляется mex.
3. И полученное в итоге значение $$$\mathrm{mex}(b_1, \ldots, b_n)$$$ берется в качестве номера секретного ингредиента.

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

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

Когда Зельду бросили в тюрьму самозванцы, притворяющиеся королем и министром Хайрула, ей было долгое время нечем заняться. Поэтому она выписала последовательность из n натуральных чисел, после чего стала выполнять с ней следующие действия:

• Каждое нечетное действие Зельда находит минимальное число в последовательности m₁, а также второе по величине значение m₂ > m₁, после чего заменяет один из элементов последовательности, равный m₁, на m₂.
• Аналогично, каждое четное действие она находит максимальное число M₁ и заменяет одно из его вхождений в последовательность на второй максимум M₂ < M₁.

Как только в последовательности останется не более двух различных чисел, Зельде надоест развлекаться с ней, и она наконец-то начнет предпринимать попытки сбежать из тюрьмы.

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

Зельда нашла способ соптимизировать создание эхо объектов и создала конвейер по их производству.

Конвейер работает почти что по принципу обычной очереди, но также обладает и некоторыми дополнительными функциями: например, если где-то в очереди скопилось много эхо, которые Зельде уже не понадобятся, есть способ их быстро из очереди изъять.

Более подробно, конвейер в каждый момент времени может быть разделен на несколько сегментов, содержащих отрезки подряд идущих элементов очереди. Для работы с конвейером доступны следующие операции:

1. добавить элемент $$$x$$$ в конец последнего сегмента очереди;
2. получить первый элемент первого сегмента очереди и удалить первый элемент каждого сегмента очереди; если какой-то сегмент после этого становится пустым, он удаляется, а его левый и правый соседи становятся соседними друг с другом;
3. разделить $$$i$$$-й по порядку сегмент очереди на первые $$$j$$$ элементов и все оставшиеся; при такой операции $$$i$$$-й сегмент разбивается на два, а относительный порядок сегментов не меняется;
4. соединить все сегменты обратно в один сегмент, содержащий все элементы очереди.

Иными словами, порядок сохранившихся элементов в очереди не меняется, а при выполнении операции pop (2) помимо изъятия самого первого элемента очереди, также удаляются первые элементы каждого сегмента.

Для тестирования конвейера Зельда просит вас реализовать структуру данных, поддерживающую все эти операции.

И вот Зельда зашла в новую локацию, и перед ней внезапно появилось $$$n$$$ противников: засада Нулла, не иначе. Для удобства в бою Зельда дала каждому противнику свой номер, кроме этого она быстро выяснила вид каждого противника. Вид противника с номером $$$i$$$ равен $$$k_i$$$, при этом у разных противников может быть один и тот же вид.

Поскольку на Зельду напали внезапно, она не смогла основательно подготовиться к сражению. Однако, благодаря наблюдениям за сражениями Линка, Зельда смогла вспомнить, что некоторые противники образуют между собой связи, делающие их уязвимыми к атакам. Значит, при правильной стратегии можно победить всех одним ударом!

К несчастью, Зельда не очень внимательно следила за сражениями Линка, поэтому смогла заметить лишь $$$n - 1$$$ связь и тот факт, что любые два противника связаны напрямую или косвенно (по цепочке).

Из-за частых конфликтов с отцом принцесса не очень сильна в комбинированных атаках, которые поражают многих врагов за раз. А именно, она может выбрать два вида противников $$$k_i$$$ и $$$k_j$$$, после чего выстрелить в какого-либо врага. Как только выстрел долетает до врага,

1. если этот враг не одного из двух выбранных видов, то с ним ничего не происходит;
2. иначе, этот враг оказывается повержен, а атака той же силы применяется к связанным с ним врагам(Зельда может выбрать, на кого перейдёт атака);
3. для каждого врага, который был атакован по цепочке связей, рекурсивно применяется тот же алгоритм.

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

Зельда хочет победить за наименьшее количество атак, так как она хочет поскорее прийти на помощь Линку. Она неплохо стреляет, но не уверена, какие виды противников выбирать для каждой атаки и кого ей нужно атаковать. Помогите Зельде с планом битвы, чтобы у неё точно получилось спасти Линка и весь Хайрул.

Зельда хочет улучшить свойства своего Жезла Трифа и собирается использовать для этого дерево, растущее у Источника Силы. Для этого ей нужно отнести священное бревно мастеру-гному. Добравшись к дереву через весь Хайрул, она обнаружила, что это довольно большое дерево, и если она возьмет его с собой целиком, то оно превысит вместимость её рюкзака на $$$w$$$ единиц вместимости.

Где-то в своём арсенале Зельда нашла заклинание, которое на час превращает её в бобра, и теперь она собирается им наконец-то воспользоваться!

Дерево магическое (подвешенное), состоит из $$$n$$$ вершин с корнем в вершине $$$1$$$, а каждая вершина имеет свой вес $$$a_i$$$.

За одно действие Зельда-бобер может выбрать некоторую вершину дерева $$$v$$$ и откусить её со всеми её отростками (вершина $$$a$$$ является отростком вершины $$$b$$$, если кратчайший путь от вершины $$$a$$$ до корня проходит через вершину $$$b$$$).

Помогите Зельде-бобру использовать заклинание так, чтобы суммарный вес всех откушенных ею вершин был в точности равен $$$w$$$.

У принцессы Зельды была колода из $$$n$$$ карт. На каждой карте было написано целое число от $$$1$$$ до $$$n$$$, причём изначально не было двух карт с одинаковыми числами на них. Затем она использовала силу волшебного Жезла Трифа и создала копию каждой карты.

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

Просто перевернуть все карты было бы слишком скучно, поэтому Зельда решила выбирать по две карты и смотреть, совпали ли их значения. Если совпали, то она их откладывает в сторону, и выбирает следующую пару карт. Иначе она переворачивает эти карты обратно и выбирает пару карт заново.

Единственное, что Зельде известно изначально — если пронумеровать все лежащие на земле карточки от $$$1$$$ до $$$2n$$$, то значение на карточке под номером $$$a$$$ строго меньше, чем на карточке под номером $$$b$$$.

Несмотря на желание сделать процесс сортировки карт интересным, принцесса очень спешит, поэтому хочет закончить за не более чем $$$2n - 1$$$ ход. Помогите ей в этом!

В процессе взаимодействия с интерактором ваша программа должна сообщать интерактору запросы в формате «? $$$x$$$ $$$y$$$», где $$$x$$$ и $$$y$$$ — два различных целых числа от $$$1$$$ до $$$2n$$$, обозначающие номера карточек, которые Зельда должна перевернуть на очередном ходу.

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

Если какой-то из сделанных вашей программой запросов будет некорректен, интерактор выведет «-1 -1» и завершится с вердиктом WA (Wrong Answer). Также если ваша программа превысит лимит в $$$2n - 1$$$ запрос, интерактор завершится тем же образом.

Если же ваша программа сможет на $$$2n - 1$$$ запрос или меньше перевернуть все карточки по парам с одинаковыми значениями, интерактор завершится с вердиктом OK. Во избежание получения вердиктов TL (Time Limit Exceeded) или IL (Idleness Limit Exceeded) ваша программа также должна завершаться с кодом возврата $$$0$$$ после успешного ответа интерактора на последний запрос.

Также обратите внимание, что вывод каждого запроса должен завершаться переводом строки (символ '{\}n') и сбросом буфера вывода (sys.stdout.flush() в Python, cout.flush() в C++, System.out.flush() в Java и аналогичными методами в других языках).