Алгоритмы на графах

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

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат входных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

Однажды Юрик оказался в лесу у костра, где собрались \(n\) человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от \(1\) до \(n\). Обозначим как \(d_i\) количество людей, сидящих у костра, с которыми знаком \(i\)-й человек. Неожиданно оказалось, что два человека с номерами \(i\) и \(j\) (\(i \ne j\)) знакомы друг с другом тогда и только тогда, когда \(d_i = d_j\).

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

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

Формат выходных данных
Выведите одно целое число — минимальное количество пар знакомых людей.

Замечание
Рассмотрим первый пример из условия. Возможны следующие варианты:

1. Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).

2. Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

Планируется строительство новой магистрали <<Урал>>. Долговечность автомагистрали зависит от пластов пород, залегающих под ней. Пластом называется геологическое тело, состоящее из одной горной породы.

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

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

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

Формат входных данных
Первая строка входного файла содержит целое число \(n\) "— количество пластов. Пласты пронумерованы целыми числами от \(1\) до \(n\) в произвольном порядке.

В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (\(0 \leqslant l_i < r_i\leqslant 10^9\)) "— расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.

В следующей строке записано целое число \(m\) "— количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (\(0 \leqslant x \leqslant 10^9\)) и \(k\) (\(0 \leqslant k \leqslant n\)) "— расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем "— целые числа \(s_1, s_2, \ldots, s_k\) "— номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).

Гарантируется, что решение существует.

Формат выходных данных
Первая строка выходного файла должна содержать \(n\) целых чисел \(p_1, p_2, \ldots , p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1, p_2, \ldots , p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1, \ldots ,p_{j-1}\) или ниже пластов с номерами \(p_{j+1}, \ldots , p_n\).

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

Примечание
Рисунок в условии соответствует примеру. Для приведенного примера правильным также является ответ 2 3 1 4. Обратите внимание, что тест из примера не соответствует подзадаче 1. Для того, чтобы решение было принято на проверку, оно должно проходить тест из примера, даже если решена только эта подзадача.

В развлекательном центре Е-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть \(n\) узлов, которые пронумерованы числами от 1 до \(n\). При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая "— направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок "— в левую.

После прохождения монеты по трубке ширина этой трубки уменьшается на 1. Монета не может пройти по трубке ширины 0. Если монета достигла узла, из которого она не может дальше двигаться вниз, автомат останавливается и ждёт, когда в него бросят следующую монету.

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

Панкрату понравилась игрушка, которая находится в узле с номером \(v\).

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

Формат входных данных
В первой строке задано число \(n\) — количество узлов в лабиринте. В последующих \(n\) строках заданы описания всех узлов, в \(k\)-й из этих строк описан узел с номером \(k\).

Описание \(k\)-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k < a_k \leqslant n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k = u_k = 0\). Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k < b_k \leqslant n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k = w_k = 0\).

В последней строке задано целое число \(v\) (\(1 \leqslant v \leqslant n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

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

Формат выходных данных
Выходные данные должны содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле \(v\). Если получить выбранную игрушку невозможно, выведите число \(-1\).

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

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

Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в \(K\) реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё \(N - 1\) реальностей. Для удобства они были занумерованы числами от \(1\) до \(N\), при этом его собственная реальность имеет номер \(1\), а посетить ему необходимо реальности с номерами \(2, 3, \ldots, K + 1\).

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени \(0\)). Исследование показало, что реальность с номером \(i\) ответвилась от реальности с номером \(P_i\) в момент времени \(T_i\). Из каждой реальности с номером \(i\) архимаг может переместиться

• в любую ответвившуюся от неё, то есть в любую \(j\), такую что \(P_j = i\);

• в \(P_i\), если \(i\) — не Начальная реальность.

Другими словами, возможны лишь переходы вида \(i \leftrightarrows P_i\). На каждый такой переход в любую сторону архимаг затрачивает \(T_i-T_{P_i} > 0\) условных единиц энергии.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером \(1\), посетить все реальности с номерами от \(2\) до \(K + 1\) (в любом порядке) и затем вновь вернуться в \(1\). Любую реальность при этом разрешается посещать сколько угодно раз.
Формат входных данных

Сначала вводятся два целых числа \(N\) и \(K\) (\(0 \leqslant K < N \leqslant 100\,000\)): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт \(N\) пар целых чисел, \(i\)-я пара — это \(P_i\) и \(T_i\) (\(1 \leqslant P_i \leqslant N\), \(0 \leqslant T_i \leqslant 10^6\); для Начальной реальности \(P_i=T_i=0\)).

Гарантируется, что ответвившаяся реальность появилась строго позже породившей (\(T_i > T_{P_i})\), и что маг может при желании добраться до любой из \(N\) реальностей.

Формат выходных данных
Выведите единственное число \(E\) — минимальную возможную энергию, которая потребуется архимагу для путешествия.

В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.

Игра идёт на доске с \(N\) строками и \(M\) столбцами (\(1 \le N \le 100\), \(1 \le M \le 100\)) по следующим правилам. В нижней строке, имеющей номер 1, стоит \(P\) белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, цель — достичь хотя бы одной пешкой самой верхней строки, имеющей номер \(N\) (Глеб слышал, что в этой ситуации из пешки можно сделать ферзя, а с такой силой он безусловно сможет побить все остальные чёрные фигуры).

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

Формат входных данных
Сначала вводятся четыре целых числа \(N\), \(M\), \(P\), \(K\) (\(1 \le N \le 100\), \(1 \le M \le 100\), \(0 \le P \le M\), \(1 \le K \le (N - 1)M\). Далее записано \(P\) различных чисел — номера столбцов \(p_j\) (\(1 \le p_j \le M\)), в которых стоят белые пешки. Далее идут \(K\) различных пар целых чисел — номера строк и столбцов чёрных фигур \(r_i\), \(c_i\) (\(2 \le r_i \le N\), \(1 \le c_i \le M\)).

Формат выходных данных
Если хотя бы одна пешка сможет достичь последнего ряда, выведите YES, в противном случае выведите NO.

На клетчатой доске размером \(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)\), тем самым поместив ее на удаляемую клетку.

Далекая страна содержит \(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\).

• 2 ≤ N ≤ 2000
• 0 ≤ M ≤ min(2000, N*(N-1)
• 1 ≤ Ai, Bi ≤ N
• Ai не равно Bi.
• Пары (Ai,Bi) уникальны.
• Все значения во входных данных целые числа.

• 2 ≤ N ≤ 2×105
• 0 ≤ M ≤ 2×105
• 1 ≤ Ai < Bi ≤ N
• Пары (Ai,Bi) уникальны.
• Все значения во входных данных целые числа.

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

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

По известному набору заклинаний, определите сможет ли Максимум получить все артефакты или нет.


Формат входных данных
В первой строке записано число n (2 <= n <= 1000), количество комнат. Далее идет n строк. В i-й строке описываются заклинания, хранящиеся в этой комнате. В каждой из этих строк первое число (m, 0 <= m <= 1000) обозначает количество уникальных заклинаний, которые открывают комнаты, далее записаны m уникальных чисел rooms[i](0 <= rooms[i][j] < n) -  номера комнат, которые открывают эти заклинания (0<=i<n,  1 <= общее количество заклинаний во всех комнатах <= 10000). 

Формат выходных данных
Выведите True, если Максимус может посетить все комнаты и найти все магические артефакты, или False в противном случае.

Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

На вход программы поступают числа n ( 1 ≤ n ≤ 100) - количество вершин в графе и m (1 ≤ m ≤ n(n-1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Выведите матрицу смежности заданного графа.

Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

На вход программы поступает число n (1 ≤ n ≤ 100) – количество вершин  графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности. 

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

У бинарного дерева есть три основных обхода: прямой (pre-order), центрированный (in-order) и обратный (post-order).

Прямой обход дерева — это порядок его вершин, полученный следующим рекурсивным алгоритмом:

1. Добавить корень дерева в обход.

2. Если у корня есть левый ребёнок, выписать прямой обход его поддерева.

3. Если у корня есть правый ребёнок, выписать прямой обход его поддерева.

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

Обобщим эти три варианта обхода: пусть в каждой вершине записано целое число \(x\) от \(-1\) до \(1\), обозначающее, в какой момент мы выписываем эту вершину, а именно:

• \(x = -1\): до обходов поддеревьев её детей;

• \(x = 0\): между обходами поддеревьев её детей;

• \(x = 1\): после обходов поддеревьев её детей.

Таким образом, если во всех вершинах записано \(-1\), обход является прямым, если \(0\) — центрированным, если \(1\) — обратным.

Рассмотрим дерево с \(n\) вершинами, пронумерованных от \(1\) до \(n\). Корень дерева — вершина \(1\). Изначально во всех вершинах записано число \(-1\).

В рамках исследования необходимо обработать \(q\) запросов одного из следующих типов:

1. Поменять числа в вершинах \(l, l+1, \dots, r\) на \(x\) (\(x\) равен \(-1\), \(0\) или \(1\)).

2. Сообщить, на какой позиции в текущем обходе будет стоять вершина \(i\).

Необходимо вывести ответы на все запросы второго типа.

В первой строке входных данных даны два целых числа \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)).

В следующих \(n\) строках даны по два целых числа \(L_i\) и \(R_i\) (\(0 \le L_i, R_i \le n\)) — номер левого и правого ребёнка вершины \(i\) соответственно, либо \(0\), если соответствующий ребёнок отсутствует.

Гарантируется, что \(L_i\) и \(R_i\) задают корректное бинарное дерево.

Формат входных данных
В следующих \(q\) строках даны запросы. Первое число в строке \(t\) (\(t \in \{1, 2\}\)) — тип запроса.

В случае запроса первого типа далее даны целые числа \(l\), \(r\) и \(x\) (\(1 \le l \le r \le n\), \(x\) равен \(-1\), \(0\) или \(1\)) — границы отрезка вершин, в которых меняются числа, и новое значение.

В случае запроса второго типа далее дано число \(i\) (\(1 \le i \le n\)) — номер вершины, позицию которой в обходе необходимо вывести.

Формат выходных данных
На каждый запрос второго типа выведите единственное число от \(1\) до \(n\) — позицию соответствующей вершины в обходе.

Пусть \(q_1\) — количество запросов первого типа.

• \([1, 3, 5, 2, 4]\)

• \([5, 2, 3, 4, 1]\)

• \([5, 3, 2, 4, 1]\)

Дано неориентированное дерево "— связный граф из \(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.

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из \(2\) строк и \(n\) столбцов, каждый элемент которой \(0\) или \(1\). За один ход можно поменять местами два элемента, стоящие в соседних клетках.

Более формально, будем считать, что строки матриц пронумерованы сверху вниз от \(1\) до \(2\), а столбцы — слева направо от \(1\) до \(n\). Обозначим клетку на пересечении строки \(x\) и столбца \(y\) за \((x, y)\). Будем считать две клетки \((x_1, y_1)\) и \((x_2, y_2)\) соседними, если \(|x_1 - x_2| + |y_1 - y_2| = 1\).

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

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

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

Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке вводятся \(n\) целых чисел, каждое из которых равно \(0\) или \(1\).

Следующие две строки описывают желаемый рисунок Алисы в том же формате.

Формат выходных данных
Если Алиса не ошиблась и её рисунок можно получить, найдите и выведите минимальное необходимое количество ходов, иначе выведите \(-1\).

В первом примере из условия подойдет следующая последовательность обменов:

\((2, 1), (1, 1)\)

\((1, 2), (1, 3)\)

\((2, 2), (2, 3)\)

\((1, 4), (1, 5)\)

\((2, 5), (2, 4)\)

Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен \(5\).

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

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки, вызовы функций ( sin , cos , abs , sqrt ) и имена переменных (только однобуквенные). Результат операции деления – вещественное число.

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

<имя переменной>=<значение>

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

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

Примеры

cos(z+abs(sqrt(r*sin(x+4))))
r=5
z=10
x=3

0.729

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки и вызовы функций ( sin , cos , abs , sqrt ). Результат операции деления – вещественное число.

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

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

Примеры

12+cos(sqrt(12+sin(2)))

11.100

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа, знаки арифметических операций (+-*/) и скобки произвольной вложенности. Результат операции деления – целое число.

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

Программа должна вывести значение переданного ей выражения как целое число.

Примеры

(5+20)*(98-34)/(5*8-23)

94