графы

Робинзон живет на острове, который представляет собой прямоугольник размером \(n \times m\) клеток.

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

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

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

Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.

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

Формат входных данных
В первой строке записаны числа \(n\) и \(m\) "— размеры острова с севера на юг и с запада на восток. Последующие \(n\) строк по \(m\) символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой <<.>>, а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: <<N>> "— север, <<S>> "— юг, <<E>> "— восток, <<W>> "— запад.

Формат входных данных
Выходной файл должен содержать одно число "— максимальное количество крокодилов, которых можно прогнать, не разозлив.

Пояснение к третьему примеру

Некоторые IT-компании проводят ежегодное глобальное мероприятие для сотрудников, на котором подводятся итоги года и обсуждаются ключевые точки в развитии всех проектов. В одной из компаний, на которой мы сфокусируемся, планируется обсуждение \(k\) различных ее проектов.

Для того, чтобы мероприятие прошло интересно, необходимо выбрать хороших спикеров. Есть \(n\) кандидатов, \(i\)-й из которых характеризуется своей осведомленностью о проектах — целым числом \(a_i\) от \(0\) до \(2^k - 1\). При этом некоторые из кандидатов дружат между собой, а именно, есть \(m\) пар друзей \((f_i, s_i)\).

Разумеется, всем хочется, чтобы мероприятие прошло гладко, а для этого необходимо, чтобы все спикеры попарно дружили между собой. При этом, чтобы рассказы спикеров не казались однообразными, важно, чтобы количество выбранных спикеров было как можно больше. Осведомленностью группы размера \(s\), состоящей из кандидатов \(i_1, i_2, \ldots, i_s\), называется \(a_{i_1} \oplus a_{i_2} \oplus \ldots a_{i_s}\), где \(\oplus\) — операция побитового исключающего <<ИЛИ>>. Соответственно, помимо уже описанных критериев, среди всех подходящих групп кандидатов максимального размера необходимо выбрать группу спикеров с максимальной осведомленностью.

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

Так как список кандидатов еще не утвержден окончательно и может меняться, вам надо решить эту задачу для \(t\) возможных наборов кандидатов.

Формат входных данных
В первой строке ввода находится одно целое число \(t\) — количество случаев, для которых надо решить задачу (\(1 \le t \le 120\)). Далее следует описание \(t\) наборов входных данных.

Первая строка каждого набора содержит три целых числа \(n\), \(m\) и \(k\) — количество кандидатов, количество пар друзей среди кандидатов и количество различных тем, которые будут обсуждаться на конференции, соответственно (\(1 \le n \le 40\); \(0 \le m \le \frac{n \cdot (n - 1)}{2}\); \(0 \le k \le 30\)).

Во второй строке каждого набора через пробел перечислены \(n\) целых чисел \(a_i\) — уровни осведомленности о проектах каждого из кандидатов (\(0 \le a_i \le 2^k - 1\)).

Далее следуют \(m\) строк, \(i\)-я из которых содержит два целых числа \(f_i\) и \(s_i\) — номера кандидатов, образующих \(i\)-ю пару друзей (\(1 \le f_i, s_i \le n\); \(f_i \neq s_i\)). Гарантируется, что все перечисленные пары друзей различны.

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(120\).

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

Замечание

В примере из условия:

1. в первом наборе входных данных выгодно выбрать спикеров под номерами \(3\) и \(4\) с осведомленностью \(a_3 \oplus a_4 = 3 \oplus 4 = 7\);

2. во втором наборе входных данных выгодно выбрать спикеров под номерами \(1\), \(3\) и \(4\) с осведомленностью \(1 \oplus 4 \oplus 8 = 14\);

3. в третьем наборе входных данных есть единственный способ выбрать четырех попарно дружащих спикеров: выбрать всех, кроме пятого.

На клетчатой доске размером \(n \times m\), состоящей из \(n\) строк и \(m\) столбцов, в клетке \((r, c)\), то есть на пересечении \(r\)-й сверху строки и \(c\)-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.

Каждый ход устроен следующим образом.

1. Компьютер называет целое число \(k > 0\).

2. Вы ровно \(k\) раз некоторым образом выбираете одну из еще не удаленных клеток, соседних по стороне (имеющих общую сторону) с той, в которой фишка находится в текущий момент, и перемещаете фишку в эту клетку. Вы можете перемещать фишку на клетку, в которой она уже была. Если не существует еще не удаленных клеток, соседних по стороне с текущей, перемещение не производится.

3. Компьютер называет координаты \((i, j)\) произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки \((i, j)\) существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке \((i, j)\), вы можете сообщить компьютеру, что игра завершена, и вы победили.

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

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

Формат входных данных
В единственной строке ввода даны четыре целых числа \(n\), \(m\), \(r\) и \(c\) — размеры доски и координаты изначального расположения фишки (\(1 \le r \le n \le 1000\); \(1 \le c \le m \le 1000\)).

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

В следующих \(n \cdot m\) строках даны ходы, которые последовательно собирается сделать компьютер. Описание \(t\)-го хода задается тремя целыми числами \(k_t\), \(i_t\) и \(j_t\) — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить (\(1 \le k_t \le 10^9\); \(1 \le i_t \le n\); \(1 \le j_t \le m\)).

Гарантируется, что все удаляемые клетки различны, то есть никакая клетка не удаляется дважды.

Формат выходных данных
Выведите одно целое число от \(1\) до \(n \cdot m\) — номер хода, после которого вы сообщите компьютеру о своей победе.

 

В первом примере можно, например, первым ходом передвинуть фишку из \((1, 1)\) в \((1, 2)\), а вторым — из \((1, 2)\) в \((2, 2)\) и затем в \((2, 1)\), тем самым поместив ее на удаляемую клетку.

Алиса и Боб играют в очень интересную карточную игру. На каждой карте в этой игре написано одно целое число. На протяжении игры у Боба в каждой из двух рук находится ровно одна карта. Изначально Боб держит в левой руке карту с числом 0, а в правой руке — также карту с числом 0.

Алиса делает \(n\) ходов. На ходу с номером \(i\) она предлагает Бобу карту с числом \(k_i\), а также 4 числа \(a_i\), \(b_i\), \(c_i\), \(d_i\). Боб выбирает, в какую руку он хочет взять новую карту, после чего выбрасывает карту из этой руки и берет в эту руку новую карту Алисы. После этого Алиса проверяет карты Боба. А именно, пусть он в левой руке держит карту \(x\), а в правой — карту \(y\). Тогда должно выполняться \(a_i \le x \le b_i\) и \(c_i \le y \le d_i\), иначе игра немедленно заканчивается.

Боб заранее знает все числа \(k_i\), \(a_i\), \(b_i\), \(c_i\) и \(d_i\). Помогите ему выбрать для каждого хода, в левую или правую руку ему следует класть очередную карту, чтобы в итоге все условия Алисы были выполнены.

В первой строке вводятся два целых числа \(n\) и \(m\) (\(2 \le n \le 100\,000\), \(2 \le m \le 10^9\)) — количество ходов в игре и максимально возможное число, записанное на карте.

Далее следует описание \(n\) ходов. Каждое описание состоит из трех строк.

Формат входных данных
В первой строке описания \(i\)-го запроса вводится целое число \(k_i\) (\(0 \le k_i \le m\)) — число, записанное на новой карте.

Во второй строке описания \(i\)-го запроса вводятся два целых числа \(a_i\) и \(b_i\) (\(0 \le a_i \le b_i \le m\)) — минимальное и максимальное допустимые значения для карты из левой руки после хода \(i\).

В третьей строке описания \(i\)-го запроса вводятся два целых числа \(c_i\) и \(d_i\) (\(0 \le c_i \le d_i \le m\)) — минимальное и максимальное допустимые значения для карты из правой руки после хода \(i\).

Формат выходных данных
Если Боб не сможет удовлетворить все условия Алисы, выведите <<No>>. Иначе в первой строке выведите <<Yes>>, а затем в следующей строке выведите \(n\) чисел — в какую руку Бобу следует класть очередную карту: если Бобу нужно взять карту в левую руку, выведите 0, иначе выведите 1. В случае, если у Боба существует несколько способов удовлетворить условиям Алисы, выведите любой из них.

В первом примере из условия Боб может взять карту из первого хода в левую руку. После этого у него в руках будут карты \(3\) и \(0\), которые соответствуют ограничениям (\(0 \le 3 \le 3\) для левой руки и \(0 \le 0 \le 2\) для правой).

Карту из второго хода Боб может взять в правую руку, после чего в его руках будут карты \(3\) и \(2\), которые соответствуют ограничениям (\(0 \le 3 \le 4\) для левой руки и \(0 \le 2 \le 2\) для правой руки). Таким образом, Боб может удовлетворить всем ограничениям Алисы, и в этом случае ответ <<Yes>>.

Далекая страна содержит \(n\) городов, соединенных \(n - 1\) дорогами, при этом из любого города можно добраться до любого другого по дорогам страны.

Известно, что каждый город относится ровно к одной провинции. Город \(v\) относится к провинции \(t_v\). Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер \(1\).

Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе \(v\) он равен \(c_v\).

Вам приходят запросы двух типов:

1. Изменить провинцию, к которой относится город \(v\), на \(t_{new}\)

2. В \(k\) городах с номерами \(a_1, a_2, \ldots, a_k\) появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции \(t\), после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером \(v\), то они получат \(c_v \cdot num_v\), где \(c_v\) — коэффициент города \(v\), а \(num_v\) это количество караванов, проходящих через этот город.

Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Формат входных данных
В первой строке даны два целых числа \(n\) и \(q\) (\(2 \le n \le 200\,000, 1 \le q \le 200\,000\)) — количество городов и количество запросов.

Во второй строке дано \(n - 1\) целое число \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i < i\)), где число \(p_i\) означает, что существует дорога между городами \(i\) и \(p_i\).

В третьей строке дано \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le n\)) — номера провинций у городов.

В четвертой строке дано \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^9\)) — коэффициенты успешности грабежа.

Далее идет \(q\) строк описаний запросов. В начале каждой строки дано одно целое число \(x_i\) (\(1 \le x_i \le 2\)) — тип запроса.

1. Если \(x_i = 1\), то далее идет два целых числа \(v\) и \(t_{new}\) (\(1 \le v, t_{new} \le n\)) — номер города, у которого меняется провинция, и номер его новой провинции.

2. Если \(x_i = 2\), то далее идут целые числа \(t\) и \(k\), и \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le t, k, a_i \le n\)) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все \(a_i\) различны. Также гарантируется, что сумма \(k\) по всем запросам второго типа не превышает \(200\,000\).

Формат выходных данных
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Примечание
В первом запросе караваны идут из городов с номерами \(3\) и \(4\) и нужно ограбить их в городе из третьей провинции. Это те же самые города с номерами \(3\) и \(4\), через каждый из которых пройдет по одному каравану. Поэтому разбойники ограбят караваны в третьем городе и получат \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

Во втором запросе караваны также идут из городов с номерами \(3\) и \(4\), но теперь нужно ограбить их в городе из первой провинции. В первой провинции находятся города \(1\) и \(2\), через каждый из которых пройдет два каравана. Среди них разбойники выбирают город \(2\), потому что \(c_2 > c_1\) и ответ на этот запрос равен \(c_2 \cdot 2 = 3 \cdot 2 = 6\).

В третьем провинция для города \(3\) изменяется на \(1\).

В четвертом запросе караваны снова идут из городов с номерами \(3\) и \(4\), и нужно ограбить караваны в городе из первой провинции. То есть разбойники могут ограбить караваны в одном из городов с номерами \(1, 2\) или \(3\). Через города с номерами \(1\) и \(2\) пройдет два каравана, а через город \(3\) только один. Разбойникам выгодно ограбить караваны в городе \(3\) и получить \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

IT-компания <<VK>> имеет огромную инфраструктуру проектов, и чтобы разработчики могли гармонично работать вместе и структурировать вносимые в код изменения, им необходима система контроля версий (VCS).

Полноценные системы контроля версий устроены достаточно сложно, и некоторые компании даже разрабатывают свои собственные VCS, заточенные под конкретные нужды или особенности рабочего процесса. Разумеется, разработчики из <<VK>> могут справиться с задачей реализовать свою VCS, но сегодня эта задача предлагается вам.

Ваша примитивная система контроля версий должна иметь вид дерева изменений состояния проекта.

• Корень дерева — стартовая вершина, соответствующая изначальному состоянию проекта. Это единственная вершина, в которую не входят ребра.

• Каждая вершина, кроме корня, соответствует определенному коммиту. Коммит — блок из одного или более изменений.

• Версия проекта, задаваемая вершиной — набор всех изменений на путях между стартовой вершиной и данной.

• Есть несколько выделенных веток, каждая имеет уникальное имя и задается указателем на определенную вершину дерева. С веткой ассоциируется версия проекта, соответствующая вершине, на которую она указывает.

• Из всех веток выделяется текущая ветка — версия проекта, с которой сейчас работает пользователь. Вершину, на которую указывает текущая ветка, будем обозначать как HEAD.

Пример дерева можно видеть ниже. Рядом с каждым коммитом указаны соответствующие ему изменения. Вершины номер \(8\) и \(9\) появляются после команды rebase между ветками <<main>> и <<new_config>> (описание команд см. ниже). Набор команд, позволяющий получить приведенную структуру графа версий, приведен в первом тесте. Пошаговые иллюстрации изменения графа версий можно видеть в прикрепленном к условию архиве.

Изначально дерево состоит из единственной вершины с номером \(1\), на которую указывает текущая ветка <<main>>. Требуется поддерживать следующие команды:

1. <<add <файл> <хеш изменений>>> — запомнить изменения, внесенные в данный файл. Хеш однозначно описывает набор изменений в файле. Иными словами, хеши двух независимых изменений совпадают тогда и только тогда, когда в файл были внесены одинаковые изменения.

   Иными словами, если в пустой файл добавляется строчка <<print(something)>>, и в непустой файл добавляется та же строчка, хеши этих двух изменений будут различными.

2. <<commit>> — подвесить к HEAD новую вершину, состоящую из всех изменений (add), сделанных с момента предыдущего успешного коммита. Новой вершине присваивается первый неиспользованный натуральный номер, после чего HEAD перемещается на нее.

   Операция возможна только тогда, когда множество сделанных изменений непустое. В противном случае требуется выдать ошибку <<FAILURE: no changes>>, при этом новая вершина не создается.

3. <<reset <номер>>> — переместить HEAD на вершину с данным номером.

   Гарантируется, что вершина с данным номером существует. Если присутствуют несохраненные (commit) изменения (add), операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>.

4. <<checkout <имя ветки>>> — поменять текущую ветку на ветку с указанным именем (и, соответственно, переместить HEAD на версию, соответствующую выбранной ветке). Если ветки с таким именем не существует, создать новую ветку с таким именем, которая будет указывать на HEAD, после чего сделать ее текущей.

   Если присутствуют несохраненные изменения, операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>, аналолгично операции reset.

5. <<rebase <имя ветки>>> — перенести изменения из ветки с указанным именем в текущую ветку. При этом находится ближайший общий предок двух веток и все коммиты в укзанной ветке после общего предка (то есть все вершины, которых нет в текущей ветке) копируются и вставляются в текущую ветку после HEAD в исходном порядке. HEAD при этом перемещается на последнюю из скопированных вершин, а указатель второй ветки не двигается. Гарантируется, что имя второй ветки не совпадает с текущей.

   Если есть незакоммиченные изменения, операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>.

   Если несохраненных изменений нет, проверяется отсутствие конфликтов при объединении. Конфликтом считается ситуация, когда в состояниях проекта, соответствующим данным веткам, с одним и тем же файлом сделаны различные изменения. Иными словами, если обозначить множество изменений определенного файла в текущей ветке как \(D_1\), а во второй — как \(D_2\), то конфликт возникает, когда оба множества \(D_1 \setminus D_2\) и \(D_2 \setminus D_1\) непустые. В таком случае операция отклоняется с ошибкой <<FAILURE: conflicts detected>>.

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

   Если какое-то изменение содержится в версиях разное ненулевое количество раз (например, изменение может присутствовать дважды после rebase двух веток, в которые оно входило), конфликт не возникает. Конфликт возникает только если в каждой версии есть измененение одного и того же файла, которого нет в другой версии.

   Ниже можно найти иллюстрации к успешным и конфликтным вызовам операции rebase.

   

   

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово <<SUCCESS>> и номер вершины, на которую указывает HEAD, если команда выполнена успешно, или же соответствующую ошибку, если команда отклонена.

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных, которые вам предстоит обработать (\(1 \le T \le 20\)). Далее следуют описания наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное целое число \(n\) — количество команд в наборе (\(0 \le n \le 400\)). В \(i\)-й из следующих \(n\) строк задается \(i\)-я команда.

Гарантируется, что имена веток состоят только из маленьких латинских букв (‘a’ – ‘z’) и нижних подчеркиваний (‘_’), а хеши изменений — уникальные шестнадцатеричные строки длины ровно \(6\) (состоят из цифр и маленьких латинских букв от ‘a’ до ‘f’). Имена файлов в команде add состоят из маленьких латинских букв, точек и слешей (‘/’).

Также гарантируется, что команде reset всегда передается существующая вершина, а команде merge — существующая ветка, не совпадающая с текущей.

Формат выходных данных
Для каждого набора входных данных в порядке их следования во вводе сначала выведите строку <<Test case <номер>>> (наборы нумеруются от \(1\) до \(T\)), а затем \(n\) результатов выполнения команд, каждый в своей строке.

Результат выполнения каждой команды должен соответствовать либо формату <<SUCCESS <HEAD>>>, либо формату <<FAILURE: <сообщение об ошибке>>>.

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

IT-компания <<VK>> имеет огромную инфраструктуру проектов, и чтобы разработчики могли гармонично работать вместе и структурировать вносимые в код изменения, им необходима система контроля версий (VCS).

Полноценные системы контроля версий устроены достаточно сложно, и некоторые компании даже разрабатывают свои собственные VCS, заточенные под конкретные нужды или особенности рабочего процесса. Разумеется, разработчики из <<VK>> могут справиться с задачей реализовать свою VCS, но сегодня эта задача предлагается вам.

Ваша примитивная система контроля версий должна иметь вид ацикличного ориентированного графа изменений состояния проекта.

• <<Исток>> графа — стартовая вершина, соответствующая изначальному состоянию проекта. Это единственная вершина, в которую не входят ребра.

• Каждая вершина, кроме корня, соответствует определенному коммиту. Коммит — блок из одного или более изменений.

• Версия проекта, задаваемая вершиной — набор всех изменений на путях между стартовой вершиной и данной.

• Есть несколько выделенных веток, каждая имеет уникальное имя и задается указателем на определенную вершину графа. С веткой ассоциируется версия проекта, соответствующая вершине, на которую она указывает.

• Из всех веток выделяется текущая ветка — версия проекта, с которой сейчас работает пользователь. Вершину, на которую указывает текущая ветка, будем обозначать как HEAD.

Пример графа можно видеть ниже. Рядом с каждым коммитом указаны соответствующие ему изменения. Вершина номер \(8\) соответствует команде merge между ветками <<main>> и <<new_config>> (описание команд см. ниже). Набор команд, позволяющий получить приведенную структуру графа версий, приведен в первом тесте. Пошаговые иллюстрации изменения графа версий можно видеть в прикрепленном к условию архиве.

Изначально граф состоит из единственной вершины с номером \(1\), на которую указывает текущая ветка <<main>>. Требуется поддерживать следующие команды:

1. <<add <файл> <хеш изменений>>> — запомнить изменения, внесенные в данный файл. Хеш однозначно описывает набор изменений в файле. Иными словами, хеши двух независимых изменений совпадают тогда и только тогда, когда состояния файла до и после изменения одинаковы.

   Иными словами, если в пустой файл добавляется строчка <<print(something)>>, и в непустой файл добавляется та же строчка, хеши этих двух изменений будут различными.

2. <<commit>> — подвесить к HEAD новую вершину, состоящую из всех изменений (add), сделанных с момента предыдущего успешного коммита. Новой вершине присваивается первый неиспользованный натуральный номер, после чего HEAD перемещается на нее.

   Операция возможна только тогда, когда множество сделанных изменений непустое. В противном случае требуется выдать ошибку <<ERROR: no changes>>, при этом новая вершина не создается.

3. <<reset <номер>>> — переместить HEAD на вершину с данным номером.

   Гарантируется, что вершина с данным номером существует. Если присутствуют несохраненные (commit) изменения (add), операция отклоняется с ошибкой <<ERROR: uncommitted changes>>.

4. <<checkout <имя ветки>>> — поменять текущую ветку на ветку с указанным именем (и, соответственно, переместить HEAD на версию, соответствующую выбранной ветке). Если ветки с таким именем не существует, создать новую ветку с таким именем, которая будет указывать на HEAD, после чего сделать ее текущей.

   Если присутствуют несохраненные изменения, операция отклоняется с ошибкой <<ERROR: uncommitted changes>>, аналолгично операции reset.

5. <<merge <имя ветки>>> — объединить изменения в текущей ветке и в ветке с указанным именем. При этом создается новая вершина, которая подвешивается к HEAD и к вершине, соответствующей второй ветке. HEAD при этом перемещается на новую вершину, а указатель второй ветки не двигается. Гарантируется, что имя второй ветки не совпадает с текущей.

   Если есть незакоммиченные изменения, операция отклоняется с ошибкой <<ERROR: uncommitted changes>>.

   Если несохраненных изменений нет, проверяется отсутствие конфликтов при объединении. Конфликтом считается ситуация, когда в состояниях проекта, соответствующим данным веткам, с одним и тем же файлом сделаны различные изменения. Иными словами, если обозначить множество изменений определенного файла в текущей ветке как \(D_1\), а во второй — как \(D_2\), то конфликт возникает, когда оба множества \(D_1 \setminus D_2\) и \(D_2 \setminus D_1\) непустые. В таком случае операция отклоняется с ошибкой <<ERROR: conflicts detected>>.

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

   Если какое-то изменение содержится в версиях разное ненулевое количество раз (например, изменение может присутствовать дважды после merge двух веток, в которые оно входило), конфликт не возникает. Конфликт возникает только если в каждой версии есть измененение одного и того же файла, которого нет в другой версии.

   Ниже можно найти иллюстрации к успешным и конфликтным вызовам операции merge.

   

   

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово <<OK>> и номер вершины, на которую указывает HEAD, если команда выполнена успешно, или же соответствующую ошибку, если команда отклонена.

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных, которые вам предстоит обработать (\(1 \le T \le 20\)). Далее следуют описания наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное целое число \(n\) — количество команд в наборе (\(0 \le n \le 400\)). В \(i\)-й из следующих \(n\) строк задается \(i\)-я команда.

Гарантируется, что имена веток состоят только из маленьких латинских букв (‘a’ – ‘z’) и нижних подчеркиваний (‘_’), а хеши изменений — уникальные шестнадцатеричные строки длины ровно \(6\) (состоят из цифр и маленьких латинских букв от ‘a’ до ‘f’). Имена файлов в команде add состоят из маленьких латинских букв, точек и слешей (‘/’).

Также гарантируется, что команде reset всегда передается существующая вершина, а команде merge — существующая ветка, не совпадающая с текущей.

Формат выходных данных
Для каждого набора входных данных в порядке их следования во вводе сначала выведите строку <<Test case <номер>>> (наборы нумеруются от \(1\) до \(T\)), а затем \(n\) результатов выполнения команд, каждый в своей строке.

Результат выполнения каждой команды должен соответствовать либо формату <<OK <HEAD>>>, либо формату <<ERROR: <сообщение об ошибке>>>.

Дано неориентированное дерево "— связный граф из \(n\) вершин без циклов, и число \(k\). Зафиксируем некоторую вершину \(s\) дерева и назовем ее столицей.

Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро \((u, v)\) в направлении \(u \to v\), если при подвешивании дерева за вершину \(s\) вершина \(u\) является родителем вершины \(v\). Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы.

Определим расстояние до вершины \(v\) графа как минимальное количество ребер на пути из \(s\) в \(v\). Назовем доступностью вершины \(s\) максимальное из расстояний до всех вершин.

Разрешается добавить в дерево не более \(k\) дополнительных ориентированных ребер.

Для каждой вершины \(s\) дерева определите, какой минимальной доступности можно достичь, если выбрать вершину \(s\) в качестве столицы.

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

Формат входных данных
Первая строка содержит три целых числа \(n\), \(k\) и \(t\) (\(2 \le n \le 2 \cdot 10^5\), \(1 \le k \le n - 1\), \(n \cdot k \le 2 \cdot 10^5\), \(0 \le t \le 1\)) — количество вершин дерева, ограничение на максимальное количество добавленных ребер и число \(t\), равное \(0\), если нужно вывести ответ только для вершины с номером \(1\), и равное \(1\) иначе.

Каждая из следующих \(n - 1\) строк содержит два целых числа \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) — ребра дерева.

Гарантируется, что заданные ребра образуют дерево.

Формат выходных данных

В случае, если \(t = 0\), выведите единственное целое число: минимальную доступность, которую можно достичь, выбрав вершину с номером \(1\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

В случае, если \(t = 1\), выведите \(n\) чисел: \(i\)-е число равняется минимальной доступности, которую можно достичь, выбрав вершину \(i\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

На рисунке приведены иллюстрации к первому примеру. Пунктирными линиями обозначены добавленные ребра. Для вершин \(1\) и \(2\) минимальная доступность равняется \(1\), а для вершин \(3\), \(4\) и \(5\) минимальная доступность равняется 2.

Миссия космолёта “Юрий Гагарин” определена - посещение трех звёздных систем в глубоком космосе. Эти звёзды находятся на Земном небосводе в созвездии Орион:

•  звезда Беллатрикс (250 световых лет от Земли)
•  звезда Бетельгейзе (643 световых года от Земли)
•  парная звёздная система Ригель (773 световых года от Земли)

Маршрут путешествия должен предусматривать посещение их в порядке удаления от Земли. Однако гиперсветовой прыжок не может пока быть выполнен с приемлемой точностью на расстояние 20 и более световых лет. Спланированная трасса полёта должна состоять из серии
прыжков, каждый прыжок менее безопасного расстояния. Вторым ограничением является то, что промежуточные точки трассы должны находиться в окрестности массивного тела, т.е. звезды. Такие звёзды в навигации называются контрольными пунктами.
Необходимо учитывать, что управление выходом из гиперпространства невозможно без существенного искривления его в точке назначения гравитационным воздействием звезды контрольного пункта. Эта особенность налагает дополнительное ограничение на каждый
выполняемый гиперпрыжок: траектория прыжка не должна проходить меньше одного светового года от звёздной системы, не являющейся контрольным пунктом.
Задача : построить трассу в трёхмерном пространстве с минимально возможным количеством гиперпрыжков, при соблюдении указанных выше ограничений. Если таких трасс несколько, то следует выбрать ту, в которой суммарная длина трассы меньше.

Входные данные
Первая строка : натуральное число N - количество звезд, внесённых в лоцию (от 3 до 100).
Далее N строк, каждая содержит три целых числа, записанных через пробел: координаты X Y Z, заданные в световых годах. Все значения координат не превышают 10000. Точка старта (0 0 0) - звезда Солнце - не указана в лоции.
Три посещаемые звёздные системы находятся в лоции в порядке ожидаемого посещения, в строках с номерами 1, 2 и 3.

Выходные данные
Первая строка: через пробел должны быть указаны количество прыжков и длина трассы с точностью до третьего знака после запятой.
Вторая строка: номера звёзд-”контрольных пунктов” и звёзд-”целей миссии” в порядке следования звездолёта, записанные через пробел.
Примечание: для отработки алгоритма построения маршрута космолёта в лоцию (комплект навигационной информации для судовождения) могут включаться различные произвольные координаты, не соответствующие известным звёздам.
В рамках задачи считать, что движение космолёта между контрольными точками происходит прямолинейно.

 

Примеры

№	Входные данные	Выходные данные
1	3 10 10 10 20 20 20 30 30 30	3 51.962 1 2 3
2	5 20 0 0 10 0 0 40 0 0 30 0 0 50 0 0	4 40.000 2 1 4 3

Рассмотрим строки, состоящие из первых k букв английского алфавита. Некоторые пары букв называются коммутирующими: если они стоят рядом в строке, их разрешается поменять местами.
Даны пары коммутирующих букв и две строки равной длины s и t. Требуется выяснить, можно ли получить t из s, выполнив произвольное количество операций: поменять местами две рядом стоящие коммутирующие буквы.

Входные данные
Первая строка содержит два целых числа k и n — количество используемых букв и количество пар коммутирующих букв (2 ≤ k ≤ 10, 0 ≤ n ≤ k(k − 1)/2).
Следующие n строк содержат по две буквы, не разделенные пробелом: пары коммутирующих букв. Гарантируется, что каждая пара приведена во вводе не более одного раза.
Следующие две строки содержат строки s и t, они имеют равную длину L (1 ≤ L ≤ 100 000) и состоят из первых k букв латинского алфавита.

Выходные данные
Выведите «YES», если строку t можно получить из строки s описанными операциями.
В противном случае выведите «NO».
 

Примеры

№	Входные данные	Выходные данные
1	3 2 ab bc abbcabc abcacbb	YES
2	3 2 ab bc abbcabc aabbbcc	NO

Мальчик Коля любит графы, но не любит циклы. У Коли есть несколько ориентированных не обязательно связных
графов. Графы могут содержать параллельные ребра, но не содержат петли. К сожалению, некоторые из них могут содержать
циклы.
Коля хочет развернуть некоторые ребра в каждом графе, чтобы избавиться от циклов. Разворотом ребра будем считать
замену ребра из вершины a в вершину b на противоположное ребро, которое будет направлено из вершины b в вершину a. При
этом Коля хочет развернуть наименьшее число ребер в каждом графе, чтобы получившиеся графы не содержали циклов.
Помогите Коле узнать, какое наименьшее число ребер ему нужно развернуть в каждом графе.

Входные данные
В первой строке входных данных содержится число t - число графов (1≤t≤8).
В первой строке описания каждого графа дано два числа n и m - число вершин и число ребер соответственно
(2≤n≤10, 1≤m≤1000).
В следующих m строках содержатся пары чисел a_i, b_i - описание ребер графа (1≤ a_i, b_i ≤ n, a_i ≠ b_i).
Для удобства, описания графов разделены пустыми строками. Пустой строки после последнего графа нет.
Гарантируется, что суммарное число вершин во всех графах не превосходит 50.

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

Примеры

№	Входные данные	Выходные данные
1	4 2 2 1 2 2 1 4 2 1 4 4 3 3 3 1 2 2 3 3 1 3 5 1 2 2 3 3 1 2 3 1 3	1 0 1 1

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

У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ. 
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.

Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).

Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.

Тесты разделены пустой строкой для читабельности.

Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 5 4 1 2 2 3 1 4 3 5	3	G′ может быть равен G′ или одному из двух следующих графов: 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5
2	7 4 6 1 2 2 3 3 4 1 3 2 4 1 4 5 5 1 2 2 3 3 4 4 5 1 5 5 7 1 2 1 3 1 5 2 4 3 3 3 4 4 5 6 6 1 2 2 3 3 4 4 5 5 6 6 6 6 7 1 2 2 3 1 3 1 4 4 5 5 6 1 6 10 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 22 28 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 8 3 9 8 10 10 11 10 12 10 13 10 14 11 15 12 16 13 17 14 18 9 15 9 16 9 17 9 18 15 19 19 20 15 20 16 21 21 22 16 22	45 35 11 1 15 371842544 256838540	Это пример более крупного теста. Обязательно выводите ответ по модулю \(10^9+7\). Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\).

 

                   ЭПИЗОД X: ФИРИОН НАНОСИТ ОТВЕТНЫЙ УДАР
Берляндия наконец-то окрепла после крупного поражения в войне против Стерляндии, и император Берляндии Фирион готовит атаку на противника. 
Стерляндия представляет собой определенное количество городов, соединенных двусторонними дорогами. От любого города Стерляндии можно добраться до любого другого. Никакая дорога не соединяет город с самим собой. 
Планируется следующее:
Выбирается город, на который будет производиться атака. Город уничтожают, а дороги, исходящие из него, баррикадируются. При этом Стерляндия должна потерять свою целостность. Далее одна из образованных областей подвергается атаке. При этом эта область должна составлять не менее 1/8 и не более 1/4  от оставшейся площади страны ( площадь измеряется в количестве городов в данной области).  Если при разрушении города Стерляндия сохраняет целостность, или подходящих областей не образуется, то данный город не подходит для атаки.
Фирион хочет знать сколько городов удовлетворяют выше описанным условиям, а также номера этих городов в порядке возрастания.
Входные данные
В первой строке даны два числа: n – кол-во городов в Стерляндии ( 2 <= n <= 10^3), m – количество дорог в Стерляндии ( 1 <= m <= 10^4).
Далее идут m строк, в которых задается описание дорог, а именно: в каждой строке заданы два числа: X и Y. Это означает, что город X и город Y соединены дорогой.
Выходные данные
В первой строке выведите число s  – кол-во городов, подходящих для атаки. Во второй строке выведите s чисел  - номера таких городов в порядке возрастания.
Пример

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

1 4

В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.
 

Примеры
Ввод