Вам задано взвешенное дерево (неориентированный связный граф без циклов, петель и кратных ребер) из \(n\) вершин. Ребро \(\{u_j, v_j\}\) имеет вес \(w_j\). Также, каждой вершине \(i\) присвоено значение \(a_i\).

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

Для каждого 2-пути \(p\) можно найти его профит \(\text{Pr}(p) = \sum\limits_{v \in \text{различные вершины в } p}{a_v} - \sum\limits_{e \in \text{различные ребра в } p}{k_e \cdot w_e}\), где \(k_e\) равно количеству вхождений \(e\) в \(p\). То есть, вершины учитываются ровно один раз, а ребра — столько, сколько раз каждое встречается в \(p\).

Вам необходимо ответить на \(m\) запросов. Каждый запрос является парой вершин \((qu, qv)\). Для каждого запроса найдите 2-путь \(p\) из \(qu\) в \(qv\) с максимальным профитом \(\text{Pr}(p)\).

В этой задаче вам требуется помочь Берляндской армии организовать их систему распространения приказов.

Всего в Берляндской армии есть \(n\) офицеров. Первый офицер — командующий армии, он не имеет никаких вышестоящих командующих. Любой другой офицер имеет ровно одного непосредственного командующего. Если офицер \(a\) является непосредственным командующим офицера \(b\), то можно сказать, что офицер \(b\) непосредственный подчиненный офицера \(a\).

Офицер \(x\) является подчиненным (непосредственным или по цепочке) офицера \(y\), если выполняется одно из следующих условий:

• офицер \(y\) непосредственный командующий офицера \(x\);
• непосредственный командующий офицера \(x\) является подчиненным офицера \(y\).

Например, на картинке ниже подчиненными офицера \(3\) являются: \(5, 6, 7, 8, 9\).

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

Формально, Берляндская армия может быть представлена как дерево, состоящее из \(n\) вершин, в котором вершина \(u\) соответствует офицеру с номером \(u\). Предок вершины \(u\) соответствует непосредственному командующему офицера \(u\). Корень (который имеет номер \(1\)) соответствует командующему армией.

Военное министерство Берляндии приказало вам ответить на \(q\) запросов, \(i\)-й запрос представлен в виде \((u_i, k_i)\), где \(u_i\) — это некоторый офицер, а \(k_i\) — некоторое натуральное число.

Для обработки \(i\)-го запроса представим, как приказ, отданный офицером с номером \(u_i\) распространяется по поддереву \(u_i\). Этот алгоритм очень похож на DFS (depth first search, обход в глубину).

Представим, что сейчас распространяет приказ офицер с номером \(a\). Офицер \(a\) выбирает \(b\) — одного из своих непосредственных подчиненных (то есть сына в дереве), который еще не получил приказ. Если существует несколько таких непосредственных подчиненных, тогда \(a\) выбирает офицера с минимальным индексом среди них. Офицер \(a\) отдает приказ офицеру \(b\). После этого \(b\) использует такой же самый алгоритм, чтобы распространить приказ в своем поддереве. После того, как \(b\) прекращает распространять приказ, офицер \(a\) выбирает следующего непосредственного подчиненного (при помощи такого же алгоритма). Когда \(a\) не может выбрать непосредственного подчиненного, еще не получившего приказ, офицер \(a\) прекращает распространять приказ.

Посмотрим на следующий пример:

Если офицер \(1\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке : \([1, 2, 3, 5 ,6, 8, 7, 9, 4]\).

Если офицер \(3\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: \([3, 5, 6, 8, 7, 9]\).

Если офицер \(7\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: \([7, 9]\).

Если офицер \(9\) распространяет приказ, офицеры в его поддереве получат приказ в следующем порядке: \([9]\).

Чтобы ответить на \(i\)-й запрос \((u_i, k_i)\), сформируем последовательность того, в каком порядке офицеры будут получать приказ, если \(u_i\)-й офицер начал его распространять. Ответом будет являться \(k_i\)-й элемент сформированной последовательности или -1, если в ней меньше \(k_i\) элементов.

Запросы необходимо рассматривать независимо. Запрос не затрагивает следующие запросы.

Задано корневое неориентированное дерево, состоящее из \(n\) вершин. Вершина \(1\) является корнем.

Определим массив глубин вершины \(x\), как бесконечную последовательность \([d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]\), где \(d_{x, i}\) — это количество вершин \(y\) таких, что выполняются оба следующих условия:

• \(x\) является предком \(y\);
• простой путь из \(x\) в \(y\) проходит ровно по \(i\) ребрам.

Доминирующий индекс массива глубин вершины \(x\) (или же просто доминирующий индекс вершины \(x\)) — это такой индекс \(j\), что:

• для каждого \(k < j\), \(d_{x, k} < d_{x, j}\);
• для каждого \(k > j\), \(d_{x, k} \le d_{x, j}\).

Для каждой вершины дерева вычислите ее доминирующий индекс.

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

Логические элементы бывают четырех видов: AND (И, \(2\) входа), OR (ИЛИ, \(2\) входа), XOR (исключающее ИЛИ, \(2\) входа), NOT (НЕ, \(1\) вход). Логические элементы принимают значения со своих прямых потомков (входов) и возвращают результат функции, которую они выполняют. Наташе известна логическая схема марсохода, а также то, что в ней сломался ровно один вход. Чтобы починить марсоход, ей нужно изменить значение на этом входе.

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

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

Время пути между некоторыми городами \(v\) и \(u\) — это суммарная длина дорог на кратчайшем пути из \(v\) в \(u\).

Два наиболее важных города Берляндии имеют номера \(1\) и \(n\).

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

Новая дорога может быть построена только между такими городами \(v\) и \(u\), что \(v \neq u\) и \(v\) и \(u\) еще не соединены никакой дорогой.

Они создали планы \(m\) возможных проектов. Каждый проект — это просто длина \(x\) новой дороги.

Поликарп работает главным аналитиком Министерства Транспорта Берляндии, разбираться с этими \(m\) проектами — его задача. Для \(i\)-го проекта он должен выбрать некоторые города \(v\) и \(u\) и построить новую дорогу длины \(x_i\) между ними так, чтобы время пути между самыми важными городами было максимально возможным.

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

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

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

В сети есть \(n\) узлов.

Ваш конкурент уже предложил некоторые подключения между узлами по некоторым фиксированным ценам. Эти подключения двусторонние. Всего ваш конкурент предложил \(m\) подключений. \(i\)-е из этих подключений соединяет узлы \(fa_i\) и \(fb_i\) и стоит \(fw_i\).

У вас есть список из \(k\) подключений, которые вы хотите предложить. Гарантируется, что эти подключения не образуют ни одного цикла. \(j\)-е из этих подключений соединит вершины \(ga_j\) и \(gb_j\). Эти подключения тоже двусторонние. Вы еще не определились с ценой каждого из подключений.

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

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

Выведите эту максимально возможную суммарную стоимость, или \(-1\), если она не ограничена.

Хомяк Дима обожает грызть различные объекты, среди которых клетки, коробки, авторы плохих задач и даже деревья!

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

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

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

В этом году правительство приняло решение разбить королевство на регионы. После разбиения будут существовать регионы нескольких уровней, при этом само королевство будет являться регионом первого уровня. Любой регион уровня \(i\) должен быть разделен на несколько (хотя бы два) регионов уровня \(i+1\), если это не регион последнего уровня. Каждый город должен принадлежать ровно одному региону каждого уровня. Внутри одного региона, между любыми двумя городами в нем должен существовать путь, проходящий только по городам этого региона.

Согласно исследованию, для каждого города \(i\) есть уровень важности — \(a_i\). Все регионы одного уровня должны иметь одинаковую сумму этих значений.

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

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

Вам дано дерево на \(n\) вершинах. Для каждого \(k\) от \(1\) до \(n\) включительно найдите максимально возможную мощность \(k\)-допустимого множества простых путей.

Вы играете в странную игру с Ли Ченом. У вас есть дерево с \(n\) вершинами, нарисованное на листе бумаги. Вершины дерева не пронумерованы, но различимы. Каждый из вас независимо пронумеровал вершины целыми числами от \(1\) до \(n\). Вы не знаете нумерацию друг друга.

Вы и Ли Чен выбрали по поддереву (то есть связному подграфу) в этом дереве. При этом ваше поддерево в вашей нумерации состоит из вершин \(x_1, x_2, \ldots, x_{k_1}\), а поддерево Ли Чена в его нумерации состоит из вершин \(y_1, y_2, \ldots, y_{k_2}\). Значения \(x_1, x_2, \ldots, x_{k_1}\) и \(y_1, y_2, \ldots, y_{k_2}\) известны вам обоим.

Вы хотите узнать, есть ли хотя бы одна общая вершина у ваших поддеревьев. К счастью, ваш друг Андрей знает ваши с Ли Ченом нумерации. Вы можете спросить у Андрея не более \(5\) вопросов, каждый из которых один из следующих двух типов:

• A x: Андрей посмотрит на вершину \(x\) в вашей нумерации и скажет вам ее номер в нумерации Ли Чена;
• B y: Андрей посмотрит на вершину \(y\) в нумерации Ли Чена и скажет вам ее номер в вашей нумерации.

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

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

Сначала считайте строку, которая содержит одно целое число \(t\) (\(1 \leq t \leq 100\)) — количество тестовых случаев.

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

В первой строке считайте одно целое число \(n\) (\(1 \leq n \leq 1\,000\)) — количество вершин в дереве.

Далее в каждой из следующих \(n-1\) строк считайте два целых числа \(a_i\) и \(b_i\) (\(1\leq a_i, b_i\leq n\)) — ребро дерева, которое соединяет вершины \(a_i\) и \(b_i\), в соответствии с вашей нумерацией вершин.

В следующей строке считайте одно целое число \(k_1\) (\(1 \leq k_1 \leq n\)) — количество вершин в вашем поддереве.

Следующая строка содержит \(k_1\) различных целых чисел \(x_1,x_2,\ldots,x_{k_1}\) (\(1 \leq x_i \leq n\)) — номера вершин в вашем поддереве, в соответствии с вашей нумерацией. Гарантируется, что эти вершины формируют поддерево.

Следующая строка содержит одно целое число \(k_2\) (\(1 \leq k_2 \leq n\)) — количество вершин в поддереве Ли Чена.

Следующая строка содержит \(k_2\) различных целых чисел \(y_1, y_2, \ldots, y_{k_2}\) (\(1 \leq y_i \leq n\)) — номера (в соответствии с нумерацией Ли Чена) вершин поддерева Ли Чена. Гарантируется, что вершины формируют поддерево, если мы применим скрытую перестановку Ли Чена на дереве, чтобы перенумеровать вершины.

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

Далее вы можете задавать Андрею два разных типа вопросов.

• Вы можете вывести «A x» (\(1 \leq x \leq n\)). Это значит, что Андрей посмотрит на вершину \(x\) в вашей нумерации и скажет вам, какой номер имеет эта вершина в нумерации Ли Чена.
• Вы можете вывести «B y» (\(1 \leq y \leq n\)). Это значит, что Андрей посмотрит на вершину \(y\) в нумерации Ли Чена и скажет вам, какой номер имеет эта вершина в вашей нумерации.

Вы можете задать не более \(5\) вопросов в одном тестовом случае.

Когда вы готовы отвечать, выведите «C s», где \(s\) — либо номер в вашей нумерации любой из вершин, которая есть в обоих поддеревьях, либо \(-1\), если таких нет. Вывод ответа не считается вопросом. Не забудьте сбросить буфер вывода, чтобы перейти к следующему тестовому случаю.

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

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Если программа жюри возвращает \(-1\) вместо ответа на запрос, это значит, что вы задали больше вопросов, чем разрешено, или задали недопустимый вопрос. Ваша программа должна немедленно завершиться (например, вызовом функции exit(0)). Вы получите вердикт Wrong Answer; это значит, что вы задали слишком много вопросов, или то, что вы задали некорректный запрос. Если вы это проигнорируете, вы можете получить любой другой вердикт, так как вы будете продолжать считывать из закрытого потока.

Входные данные для взломов

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

Первая строка должна содержать одне целое число \(t\) (\(t=1\)).

Вторая строка должна содержать одно целое число \(n\) (\(1 \leq n \leq 1\,000\)).

Третья строка содержит \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) (\(1\leq p_i\leq n\)) — скрытая перестановка от \(1\) до \(n\). Эта перестановка задает нумерацию, которую использует Ли Чен. То есть вершина, которая у вас имеет номер \(i\), имеет номер \(p_i\) в нумерации Ли Чена.

Каждая из следующих \(n-1\) строк должна содержать два целых числа \(a_i\) и \(b_i\) (\(1\leq a_i, b_i\leq n\)). Эти ребра должны формировать дерево.

Следующая строка должна содержать одно целое число \(k_1\) (\(1 \leq k_1 \leq n\)).

Следующая строка должна содержать \(k_1\) различных целых чисел \(x_1,x_2,\ldots,x_{k_1}\) (\(1 \leq x_i \leq n\)). Эти вершины должны формировать поддерево.

Следующая строка должна содержать одно целое число \(k_2\) (\(1 \leq k_2 \leq n\)).

Следующая строка должна содержать \(k_2\) различных целых чисел \(y_1, y_2, \ldots, y_{k_2}\) (\(1 \leq y_i \leq n\)). Эти вершины должны формировать поддерево в нумерации Ли Чена.

В неуказанной Солнечной системе есть \(N\) планет. Космическая правительственная компания недавно наняла космических подрядчиков, чтобы построить \(M\) двусторонних шоссе Hyperspace™, каждое из которых соединяет пару разных планет. Основная цель, заключавшаяся в том, чтобы убедиться, что любая планета может быть достигнута из любой другой планеты, используя только шоссе Hyperspace™, была полностью выполнена. К сожалению, у многих космических подрядчиков были друзья и двоюродные братья в космическом совете директоров компании, поэтому компания решила сделать нечто большее, чем просто соединение всех планет.

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

Вы разрабатываете навигационное приложение Hyperspace™, и ключевая техническая проблема, с которой вы столкнулись — это поиск минимального количества шоссе Hyperspace™, которыми нужно воспользоваться для путешествия из планеты \(A\) на планету \(B\). Поскольку эта задача слишком проста для Bubble Cup, вот более сложная задача: ваша программа должна сделать это для \(Q\) пар планет.

Поскольку астронавты из миссии BubbleCup XI закончили свою миссию на Луне и являются большими поклонниками известного певца, они решили провести некоторое время перед возвращением на Землю, и, таким образом, создали так называемую игру «Moonwalk challenge».

Командам астронавтов выдаются карты кратеров на Луне и прямых двунаправленных путей от одних кратеров к другим, безопасные для «лунной походки». Каждый из этих прямых путей окрашен в один цвет, и есть единственный путь между каждым из двух кратеров. Цель игры заключается в том, чтобы найти два кратера, такие, что заданный массив цветов появляется чаще всего как непрерывный подотрезок на пути между этими двумя кратерами (пересекающиеся вхождения должны быть учтены как два различных).

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

Все цвета являются строчными буквами латинского алфавита.

Эйлер — маленький милый бельчонок. Когда приходит осень, он запасается желудями на зиму. Интересный факт, что Эйлер обычно собирает желуди очень специфичным способом. Дерево, с которого он собирает желуди, можно представить как \(n\) желудей, соединенных \(n - 1\) веткой таким образом, что есть ровно один путь между каждой парой желудей. Пронумеруем желуди от \(1\) до \(n\).

Бельчонок выбирает один из желудей (не обязательно с номером \(1\)) как старт, затем обходит все желуди способом, который называется «Эйлеров обход» (см. примечание), собирая каждый из желудей, когда он посещает его в последний раз.

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

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

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

Рассмотрим все пары вершин \((v, u)\) (то есть всего \(n^2\) таких пар) и для каждой пары посчитаем побитовое исключащее ИЛИ (xor) всех чисел на рёбрах на простом пути между \(v\) и \(u\). Если путь состоял только из одной вершины, то xor всех чисел на рёбрах этого пути считается равным \(0\).

Предположим, мы отсортировали полученные \(n^2\) значений по неубыванию. Требуется вывести \(k\)-е из них.

Операция xor определяется следующим образом:

Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\) (где \(k\) любое число, что все биты \(x\) и \(y\) могут быть представлены). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\).

Пусть \(r = x \oplus y\) — результат операции xor над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:

\(\) r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. \(\)

Когда-то давно в небезызвестной компании Bmail был только один маршрутизатор. Шли года и с течением времени закупались новые маршрутизаторы. Каждый раз при покупке нового маршрутизатора он соединялся с одним из купленных до него. Вам заданы значения \(p_i\) — номер маршрутизатора к которому был подключен \(i\)-й после покупки (\(p_i < i\)).

Сейчас в Bmail всего \(n\) маршрутизаторов. Выведите последовательность маршрутизаторов на пути от первого до \(n\)-го.

Мэр уездного города N Сергей Семёнович днями и ночами думает об улучшении жизни Nчан. К сожалению, все мыслимые и немыслимые идеи по модернизации городского пространства уже были приведены в исполнение и больше мэру нечем занимать свой ум днём (ночью он теперь спит). Однако, его помощники быстро нашли выход из положения, они рисуют на бумаге новый город и предлагают мэру составлять проекты его улучшения.

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

Как показатель качества схемы метро, Сергей Семёнович использует сумму попарных расстояний между всеми парами станций. Расстоянием между двумя станциями называется минимально возможное количество перегонов на пути между ними.

Сергей Семёнович решил добавить в схему новые перегоны. А именно, он дорисовал перегон между станциями \(u\) и \(v\), если эти станции не были соединены перегоном напрямую, но у них была общая станция-сосед, то есть существовала такая станция \(w\), что в оригинальной схеме присутствовал перегон между \(u\) и \(w\) и перегон между \(w\) и \(v\). Вам поставлена задача вычислить сумму попарных расстояний между всеми парами станций в получившейся схеме метрополитена.

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

• спуститься к любому листу поддерева вершины \(v\);
• если вершина \(v\) — лист, то подняться вверх по дереву не более чем \(k\) раз. Другими словами, если \(h(v)\) — глубина вершины \(v\) (глубина корня равна \(0\)), то вы можете передвинуть фишку в вершину \(to\) такую, что \(to\) — некоторый предок \(v\) и \(h(v) - k \le h(to)\).

В данной задаче считается, что корень не является листом (даже если его степень равна \(1\)). Посчитайте максимальное количество различных листов, которые вы сможете посетить одной последовательностью ходов.

Задано неориентированное невзвешенное дерево, состоящее из \(n\) вершин.

Неориентированное дерево — это связный неориентированный граф с \(n - 1\) ребром.

Ваша задача — выбрать две пары вершин этого дерева (все выбранные вершины должны быть различны) \((x_1, y_1)\) и \((x_2, y_2)\) таким образом, что \(x_1\) и \(y_1\) не должны принадлежать простому пути от \(x_2\) до \(y_2\) и наоборот (\(x_2\) и \(y_2\) не должны принадлежать простому пути от \(x_1\) до \(y_1\)).

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

Среди всех возможных способов выбрать эти пары вам необходимо выбрать способ с максимальным количеством общих вершин между путями от \(x_1\) до \(y_1\) и от \(x_2\) до \(y_2\). И среди всех таких пар вам необходимо выбрать пару с максимальной суммарной длиной этих двух путей.

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

Длина пути — это количество ребер в нем.

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

У Поликарпа в записной книжке \(n\) телефонов, про каждый он знает сам номер \(s_i\) и \(m_i\) — сколько раз в день он его набирает.

Недавно Поликарп приобрел совершенно новый телефон с инновационной опцией быстрого набора! Более точно, \(k\) его клавишам можно назначить некоторый номер (не обязательно из телефонной книги). Для ввода номера Поликарп может нажать одну из этих \(k\) клавиш, а потом завершить набор номера нажатиями на обычные цифровые клавиши (ввод номера только цифровыми клавишами также возможен).

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

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

Однажды Гриша нашёл дерево (связный ациклический граф) с корнем в вершине \(1\).

Но дерево было не простое — в вершинах этого дерева записана перестановка \(p\) чисел от \(0\) до \(n - 1\), в \(i\)-й вершине записано число \(p_i\).

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

Определим функцию \(MEX(S)\), где \(S\) является множеством целых неотрицательных чисел, как наименьшее целое неотрицательное число, не входящее в множество.

Пусть \(l\) — простой путь в дереве. Тогда обозначим за \(u_1\), \(u_2\), \(\ldots\), \(u_k\) — номера вершин, принадлежащих \(l\).

Обозначим за \(V(l)\) множество {\(p_{u_1}\), \(p_{u_2}\), \(\ldots\) , \(p_{u_k}\)}.

Тогда запросы таковы:

1. Для двух вершин \(i\) и \(j\) нужно поменять местами значения \(p_i\) и \(p_j\).
2. Требуется найти максимальный \(MEX(V(l))\) по все возможным \(l\).

Вам дано дерево, состоящее из \(n\) вершин. Каждая вершина \(u\) имеет некоторый вес \(a_u\). Вы хотите выбрать целое число \(k\) \((1 \le k \le n)\), а затем выбрать \(k\) связных компонент, которые не пересекаются друг с другом (каждая вершина находится максимум в одной компоненте). Пусть вы выбрали компоненты, в совокупности содержащие множество вершин \(s\). Вы хотите максимизировать следующее значение:

\(\)\frac{\sum\limits_{u \in s} a_u}{k}\(\)

Другими словами, вы хотите максимизировать сумму весов вершин из \(s\), деленную на количество выбранных вами компонент. Также, если возможных решений несколько, вы хотите максимизировать \(k\).

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

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

Однажды Пете встретилось дерево из n вершин. При этом дерево было взвешенным, то есть каждое его ребро имело вес (целое положительное число). Ребро счастливое, если его вес — счастливое число. Напомним, что дерево из n вершин — это неориентированный связный граф, у которого ровно n - 1 ребер.

Пете стало интересно, сколько существует таких троек вершин дерева (i, j, k), что и на пути из i в j, и на пути из i в k есть хотя бы одно счастливое ребро (все три вершины попарно различны). Порядок чисел в тройке имеет значение, то есть тройка (1, 2, 3) не равна тройке (2, 1, 3) и не равна тройке (1, 3, 2).

Найдите количество таких троек.

Задано дерево, состоящее ровно из \(n\) вершин. Дерево — это связный неориентированный граф с \(n-1\) ребром. Каждой вершине \(v\) этого дерева соответствует некоторое значение \(a_v\).

Пусть \(dist(x, y)\) — расстояние между вершинами \(x\) и \(y\). Расстояние между вершинами — это количество ребер на простом пути между ними.

Определим стоимость дерева как следующую величину: сначала давайте зафиксируем одну вершину дерева. Пусть она равна \(v\). Тогда стоимость дерева равна \(\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i\).

Ваша задача — найти максимально возможную стоимость дерева, если вы можете выбирать \(v\) самостоятельно.

У Мити есть корневое дерево из \(n\) вершин, пронумерованных от \(1\) до \(n\), причем корень дерева имеет номер \(1\). В каждой его вершине \(v\) было записано целое число \(a_v \ge 0\). Для каждой вершины \(v\) Митя вычислил величину \(s_v\): сумму чисел, записанных на пути от вершины \(v\) до корня, а также \(h_v\) — глубину вершины \(v\), то есть количество вершин на пути от вершины \(v\) до корня (таким образом, \(s_1=a_1\), \(h_1=1\)).

После этого Митя уничтожил исходные значения \(a_v\). К сожалению, он также случайно уничтожил все значения \(s_v\) для вершин, находящихся на четной глубине (то есть тех, для которых \(h_v\) является четным). Ваша задача состоит в том, чтобы восстановить значения \(a_v\) для каждой из вершин либо определить, что это невозможно. Среди возможных вариантов нужно выбрать тот, при котором сумма значений \(a_v\) во всем дереве является минимально возможной.

Митя и Вася играют в интересную игру. У них есть подвешенное дерево из \(n\) вершин, пронумерованных числами от \(1\) до \(n\). В этом дереве вершина \(1\) является корнем, а родителем вершины \(i \ge 2\) является вершина \(p_i\) (при этом будем говорить, что вершина \(i\) — ребенок вершины \(p_i\)).

В каждой вершине дерева находятся печеньки, в вершине \(i\) находится \(x_i\) печенек. Чтобы съесть одну печеньку в вершине \(i\), нужно потратить \(t_i\) единиц времени. Также в игре есть одна фишка. Изначально она находится в корне дерева. Чтобы переместить фишку по ребру, соединяющему вершину \(i\) с ее родителем, нужно потратить \(l_i\) единиц времени.

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

На любом своем ходу Митя может закончить игру. После этого он двигает фишку вверх до корня, по пути съедая какие-то печеньки. Митя может потратить суммарно на спуск, подъем и поедание печенек не более \(T\) единиц времени. Обратите внимание, что в конце игры фишка всегда оказывается в корне: Митя не может оставить фишку ни в какой промежуточной вершине, даже если требуемое число печенек уже было съедено — он обязан переместить фишку в корень (и на каждое перемещение фишки по ребру из вершины \(v\) в ее предка он тратит \(l_v\) единиц времени).

Какое максимальное количество печенек Митя может съесть, независимо от действий Васи?

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

В данной задаче деревом называется взвешенный связный граф, состоящий из \(n\) вершин и \(n-1\)-го ребра, такой, что веса всех рёбер — целые числа от \(1\) до \(m\). Красоту дерева Кефа оценивает следующим образом: он находит в дереве две свои любимые врешины — вершины с номерами \(a\) и \(b\), и считает расстояние между ними. Расстоянием между двумя вершинами \(x\) и \(y\) назовём сумму весов всех рёбер на простом пути из \(x\) в \(y\). Если расстояние от вершины \(a\) до вершины \(b\) равно \(m\), то дерево красивое.

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

Кефа предупредил Сашу, что красивых деревьев очень много, поэтому достаточно будет вычислить их количество по модулю \(10^9 + 7\).

Определим эйлеров обход дерева (связного неориентированного графа без циклов) следующим образом: рассмотрим рекурсивный алгоритм поиска в глубину, который обходит вершины дерева и нумерует вершины в том порядке, в котором их посещает, при этом учитывается только первое посещение каждой вершины. Данная функция стартует из вершины с номером \(1\), а затем рекурсивно вызывается от всех вершин, которые соединены ребром с текущей и ещё не посещены, в порядке возрастания номеров вершин. Формально данную функцию можно описать так:

next_id = 1
id = массив длины n, заполненный -1
visited = массив длины n, заполненный false

function dfs(v):
    visited[v] = true
    id[v] = next_id
    next_id += 1
    for to по соседям v в порядке возрастания:
        if not visited[to]:
            dfs(to)

Дано взвешенное дерево, вершины которого пронумеровали в порядке эйлерова обхода целыми числами от \(1\) до \(n\) при помощи алгоритма, описанного выше.

Назовём листом вершину дерева, соединённую ребром ровно с одной другой вершиной. В данном вам дереве вершина \(1\) не является листом. Расстоянием между двумя вершинами дерева назовём сумму весов рёбер на единственном простом пути между ними.

Требуется ответить на \(q\) запросов следующего вида: по заданным числам \(v\), \(l\) и \(r\) сообщить кратчайшее расстояние от вершины \(v\) до одного из листов дерева, имеющего номер от \(l\) до \(r\) (включительно).

Дано дерево из \(n\) вершин и \(q\) запросов.

Каждый запрос начинается с трех целых чисел \(k\), \(m\) и \(r\), и продолжается \(k\) вершинами дерева \(a_1, a_2, \ldots, a_k\). Чтобы ответить на запрос, предположите, что дерево подвешено за вершину \(r\). Рассмотрим разбиения данных \(k\) вершин на не более чем \(m\) групп так, что выполняются следующие условия:

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

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

Задано неориентированное дерево из \(n\) вершин.

Некоторые вершины покрашены в один из \(k\) цветов, а некоторые не покрашены совсем. Гарантируется, что дерево содержит хотя бы одну вершину каждого из \(k\) цветов. Может быть ноль непокрашенных вершин.

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

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

Ответ может быть довольно большим, поэтому выведите его по модулю \(998244353\).

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

Легендарное дерево покоится глубоко в лесу. Легенда гласит, что люди, которые узнают структуру этого дерева, навсегда станут легендарными гроссмейстерами.

Чтобы помочь вам определить дерево, богиня Микаэла рассказала вам, что это дерево состоит из \(n\) вершин, пронумерованных от \(1\) до \(n\). Она также позволила вам спросить что-то про дерево. Чтобы задать вопрос, вы должны назвать Микаэле два непересекающихся непустых множеств вершин \(S\) и \(T\) и произвольную вершину \(v\). Затем Микаэла посчитает и скажет вам количество пар вершин \((s, t)\), где \(s \in S\) и \(t \in T\) таких, что простой путь от \(s\) до \(t\) содержит \(v\).

Богиня Микаэла занята и сможет ответить вам только на \(11\,111\) запросов.

Это ваш единственный шанс. Ваша задача — определить дерево и вывести его ребра.

Чтобы задать вопрос, действуйте следующим образом.

1. Сначала выведите размер множества \(S\) на отдельной строке. В следующей строке выведите \(|S|\) различных целых чисел, разделенных пробелами, описывающих вершины \(S\).
2. Затем, аналогично, выведите размер множества \(T\) на отдельной строке. В следующей строке выведите \(|T|\) различных целых чисел, разделенных пробелами, описывающих вершины \(T\).
3. Затем, в последней строке, выведите \(v\) — вершину, которую вы выбрали для этого запроса.
4. Прочитайте ответ Микаэлы из входного файла.

Не забудьте, что \(S\) и \(T\) должны быть непустыми и непересекающимися.

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

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

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

Обратите внимание, что дерево загадано заранее и не зависит от ваших запросов.

Взломы

Взломы должны быть описаны следующим образом.

Первая строка должна содержать целое число \(n\) (\(2 \leq n \leq 500\)) — количество вершин в дереве.

Следующие \(n-1\) строк должны содержать по два целых числа \(u\) и \(v\), обозначающих наличие в дереве неориентированного ребра \((u, v)\) (\(1 \leq u, v \leq n\)).

Лена играется со спичками. Естественный вопрос, посещающий любого школьника, играющего со спичками — а можно ли поджечь спичкой дерево?

Скажем, что дерево — это связный граф без циклов, вершины которого пронумерованы целыми числами \(1, 2, \ldots, n\), в каждой вершине которого также записано некоторое целое число \(p_v\), являющееся приоритетом вершины \(v\). Все приоритеты различны.

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

Лена приготовила дерево из \(n\) вершин и в каждой вершине записала приоритет \(p_v = v\). Лене с одной стороны интересно посмотреть, как горит дерево, но с другой она понимает, что если дерево поджечь, оно исчезнет насовсем. Лена добрая девочка, и деревья ей жалко, так что она хочет ограничиться выяснением ответов на некоторые вопросы про процесс сгорания дерева в уме. Лена хочет ответить на \(q\) вопросов, каждый из которых относится к одному из трёх следующих видов:

• «up \(v\)», присвоить вершине \(v\) приоритет \(1 + \max\{p_1, p_2, \ldots, p_n\}\);
• «when \(v\)», выяснить, какой по счёту сгорит вершина \(v\), если дерево поджечь сейчас;
• «compare \(v\) \(u\)», выяснить, какая из вершин \(v\) и \(u\) сгорит раньше, если дерево поджечь сейчас.

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

Вам дан неориентированный граф специального вида. Он состоит из \(2n\) вершин, пронумерованных от \(1\) до \(2n\). Граф обладает следующими свойствами:

• в нем ровно \(3n-2\) ребра: \(n\) ребер соединяют вершины с четными номерами и вершины с нечетными номерами, \(n - 1\) ребер соединяют вершины с нечетными номерами друг с другом, и \(n - 1\) ребер соединяют вершины с четными номерами друг с другом;
• для каждого ребра \((u, v)\) между вершинами с нечетными номерами существует ребро \((u + 1, v + 1)\), и наоборот;
• для каждого нечетного числа \(u \in [1, 2n - 1]\) существует ребро \((u, u + 1)\);
• граф является связным; более того, если мы удалим все четные вершины и ребра, инцидентные им, граф станет деревом (то же самое произойдет, если удалить все нечетные вершины).

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

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

Вам даны \(q\) запросов к графу; в каждом запросе требуется подсчитать длину кратчайшего пути между какой-то парой вершин. Можете ли вы справиться со всеми запросами?

Недавно Линэрд и Скинэрд отправились в магазин, где Линэрд купил себе перестановку \(p\) длины \(n\), а Скинэрд купил себе массив \(a\) длины \(m\), состоящий из чисел от \(1\) до \(n\).

Линэрду и Скинэрду скучно, поэтому они решили задать вам \(q\) вопросов, имеющих следующий вид: «есть ли у подотрезка массива \(a\) c \(l\)-й по \(r\)-ю позицию включительно подпоследовательность, которая является циклическим сдвигом \(p\)?».

Перестановка длины \(n\) — это последовательность из \(n\) чисел, в которой каждое число от \(1\) до \(n\) встречается ровно один раз.

Циклический сдвиг перестановки \((p_1, p_2, \ldots, p_n)\) — это перестановка \((p_i, p_{i + 1}, \ldots, p_{n}, p_1, p_2, \ldots, p_{i - 1})\) для какого-то \(i\) от \(1\) до \(n\). Так, например, у перестановки \((2, 1, 3)\) есть три различных циклических сдвига: \((2, 1, 3)\), \((1, 3, 2)\), \((3, 2, 1)\).

Подпоследовательность подотрезка массива \(a\) с \(l\)-й по \(r\)-ю позицию включительно — это последовательность \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) для каких-то \(i_1, i_2, \ldots, i_k\) таких, что \(l \leq i_1 < i_2 < \ldots < i_k \leq r\).

Вам дано корневое дерево с \(n\) вершинами, пронумерованными от \(1\) до \(n\). Корнем дерева является вершина \(1\). Предком \(i\)-й вершины является вершина \(p_i\). Лист — это вершина без детей. Для некоторого набора листьев \(L\) пусть \(f(L)\) обозначает наименьший связный подграф, содержащий все листья \(L\).

Вы хотите разделить листы так, чтобы для любых двух различных множеств \(x, y\) разбиения \(f(x)\) и \(f(y)\) не пересекались.

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

В компании работает n сотрудников, пронумерованных от 1 до n. У каждого сотрудника либо нет руководителя, либо есть ровно один непосредственный руководитель — некоторый другой сотрудник с другим номером. Сотрудник A называется начальником другого сотрудника B, если выполняется хотя бы одно из двух условий:

• Сотрудник A — непосредственный руководитель сотрудника B.
• У сотрудника B есть непосредственный руководитель, сотрудник C, такой, что A является начальником сотрудника C.

В структуре компании нет циклов. То есть никакой сотрудник не является начальником своего непосредственного руководителя.

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

Ваша задача — найти наименьшее возможное количество таких групп.

Теперь Сервал — младший ученик средней школы Джапари, и он все еще в восторге от математики, как и раньше.

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

Деревом называется связный граф без циклов. Подвешенное дерево имеет выделенную вершину, называемую корнем. Родителем вершины \(v\) называется последняя отличная от \(v\) вершина на пути от корня к вершине \(v\). Дети вершины \(v\) — все вершины, для которых \(v\) является родителем. Вершина называется листом, если у нее нет детей.

Подвешенное дерево Сервала имеет \(n\) вершин, корень дерева — вершина \(1\). Сервал хочет написать по одному числу в каждую из вершин, но есть некоторые ограничения. В каждой из вершин, кроме листьев, записана операция \(\max\) или \(\min\), указывающая, что число в этой вершине должно быть равно максимуму или минимуму среди всех чисел, написанных в ее детях, соответственно.

Предположим, что в дереве \(k\) листьев. Сервал хочет написать числа \(1, 2, \ldots, k\) в эти \(k\) листьев (каждое число должно использоваться ровно один раз). Он любит большие числа, поэтому он хочет максимизировать число в корне. Как его лучший друг, вы можете помочь ему?