Задача 1. Лекция. Графы. DFS. Времена входа и выхода ≡

Условие

Времена входа и выхода при обходе в глубину

Вспомним процедуру обхода графа в глубину.

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;
    Previsit(v);

    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

    Postvisit(v);
end;

Поиск в глубину позволяет за линейное время определить, связен ли граф. Но это далеко не все — сейчас мы рассмотрим прием, который лежит в основе многих других применений поиска в глубину. Будем записывать время входа в каждую вершину (вызов Previsit) и время выхода (Postvisit). Для нашего примера эти числа показаны на рис. 1. Например, в момент времени 5 началась обработка вершины I, а в момент времени 21 закончилась обработка вершины D.

Чтобы сохранить эту информацию при поиске в глубину, заведем счетчик time, изначально равный 1, и напишем так:

procedure Previsit(v: integer);
begin
    tin[v] := time;
    time += 1;
end;

procedure Postvisit(v: integer);
begin
    tout[v] := time;
    time += 1;
end;

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

Свойство. Для любых двух вершин u и v либо отрезки [tin(u), tout(u)] и [tin(v), tout(v)] не пересекаются, либо один содержится в другом.

В самом деле, [tin(u), tout(u)] — это промежуток времени, в течение которого вершина u была в стеке, и если вершина v была помещена в стек, когда там уже лежала вершина u, то v будет вынута раньше u.

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

Задача 2. Лекция. Графы. DFS в ориентированном графе. ≡

Условие

Поиск в глубину в ориентированном графе

Рассмотренный нами алгоритм поиска в глубину может быть использован и для ориентированных графов (в процедуре Explore надо перебирать выходящие из вершины ребра). На рис. 1 показан пример ориентированного графа и дерева, построенного поиском в глубину.

Вершина A называется корнем дерева (tree root), все остальные вершины этого дерева являются ее потомками E, а E является их предком (ancestor). Наконец, C является родителем (parent) D, а D — ребенком (child) C. (В отличие от людей, у вершины дерева может быть только один родитель.)

При поиске в глубину в ориентированных графах различают четыре типа ребер.

• Ребра дерева (tree edges) — ребра леса, построенного поиском в глубину.
• Прямые ребра (forward edges) ведут от вершины к ее потомку, не являющемуся при этом ее ребенком.
• Обратные ребра (back edges) ведут от вершины к ее предку.
• Перекрестные ребра (cross edges) ведут от вершины к другой вершине, не являющейся ни предком, ни потомком первой (такая вершина уже полностью обработана в момент обнаружения перекрестного ребра).

На рис. 1 можно обнаружить два прямых, два обратных и два перекрестных ребра (найдите их).

Тип ребра можно узнать по tin и tout значениям его концов. Легко видеть, что вершина u является предком v тогда и только тогда, когда v была обнаружена во время вызова Explore(u). В этом случае tin(u) < tin(v) < tout(v) < tout(u), то есть отрезок обработки v вложен в отрезок обработки u. Для обратных ребер: u — потомок v тогда и только тогда, когда v — предок u; для перекрестных ребер u−v отрезки не пересекаются (и v-отрезок предшествует u-отрезку).

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

Ориентированные ациклические графы

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

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

Доказательство. Ясно, что если (u, v) — обратное ребро, то путь в дереве поиска в глубину от v к u и само ребро (u, v) образуют цикл.

Обратно: пусть граф содержит цикл v₀→ v₁→ ... → v_k→ v₀ и пусть v_i — вершина этого цикла, которая была обнаружена первой (то есть вершина с минимальным tin(v_i)). Все оставшиеся вершины цикла достижимы из v_i, и поэтому в дереве поиска в глубину они будут потомками v_i. Тогда ребро v_i−1→ v_i (или же v_k→ v₀, если i = 0) ведет из вершины в ее предка, то есть является обратным ребром.

Топологическая сортировка

С помощью ориентированных ациклических графов (directed acyclic graphs или сокращенно DAGs) удобно представлять временные и иерархические отношения, а также причинно-следственные связи. Допустим, к примеру, что необходимо сделать несколько вещей, при чем есть ограничения на порядок (сначала надо проснуться и лишь потом встать с кровати; душ надо принять после того, как встал с кровати, но до того, как оделся). Как выбрать правильный порядок дел?

Ограничения представим как ориентированный граф: каждому делу соответствует вершина; ребро из u в v означает, что u должно быть выполнено до v. Если в этом графе есть цикл, то правильного порядка не существует вовсе. Если же граф ациклический, то есть надежда его топологически упорядочить (topologically sort) — так упорядочить вершины, чтобы каждое ребро вело от более ранней вершины к более поздней. Например, для графа рис. 2 один из допустимых порядков таков: B, A, D, C, E, F. (Видите ли вы еще три порядка?).

Какие же ориентированные ациклические графы можно топологически упорядочить? Оказывается, что все, и это можно сделать с помощью поиска в глубину, расположив вершины в порядке убывания их tout-значений. Ведь tout(u) < tout(v) только для обратных ребер (u, v), а мы уже знаем, что в ациклическом графе обратных ребер быть не может.

Свойство.В ориентированном ациклическом графе каждое ребро идет из вершины с бОльшим tout-значением в вершину с меньшим tout-значением.

Посмотрим на первую и последнюю вершину после топологической сортировки. Из последней вершины рёбра не выходят: как говорят, она является стоком (sink). Напротив, в первую вершину рёбра не входят: она является истоком (source). В частности, мы доказали такое утверждение:

Свойство.У каждого ациклического ориентированного графа есть хотя бы один исток и хотя бы один сток.

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

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;

    Previsit(v);

    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

{ Добавляем вершину в конец с помощью глобального счетчика k }
    order[k] = v;
    k += 1;
end;

Задача 3. Лекция. Графы. Компоненты сильной связности ≡

Условие

Связность для ориентированных графов

Что означает связность для ориентированного графа? Тут надо быть аккуратным. Несвязный неориентированный граф можно разбить на связные компоненты, не соединенные друг с другом. С ориентированными графами ситуация сложнее. Граф на рис. 1 нельзя разбить на две части, не соединенные друг с другом. Но мы не будем называть этот граф связным, поскольку в нем нет пути из G в B или из F в A. Дадим такое определение:

Вершины u и v ориентированного графа называются связанными (connected), если в нем есть путь из u в v, а также путь из v в u.

Такое отношение на вершинах разбивает все множество вершин на непересекающиеся подмножества связанных вершин, называемые компонентами сильной связности (strongly connected components). Граф на рис. 1 имеет пять таких компонент.

Стянем теперь каждую компоненту сильной связности в отдельную вершину (метавершину) и оставим только ребра между метавершинами (см. рис. 1), удалив дубликаты. Полученный граф называется метаграфом (meta-graph) (также графом компонент или конденсацией) исходного. Он не содержит циклов: если бы несколько компонент образовывали цикл, то вершины этих компонент были бы в исходном графе достижимы друг из друга и вошли бы в одну компоненту.

Свойство 0. Граф конденсации любого ориентированного графа является ациклическим (и может быть топологически упорядочен).

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

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

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

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

Для начала ответим на первый вопрос. Сначала покажем, как решать симметричную задачу: найти вершину в компоненте-истоке

Свойство 2. Вершина, которой поиск в глубину присваивает максимальное tout-значение, лежит в компоненте-истоке.

Свойство 3. Пусть C и C′ — компоненты сильной связности графа и в графе есть ориентированное ребро из C в C′. Тогда максимальное tout-значение вершин в C больше, чем максимальное tout-значение вершин в C′.

Доказательство. Дождемся момента, когда при поиске в глубину впервые появится вершина v из C или C′. Если v ∈ C, то вызов Explore(v) не завершится, пока не будут обработаны все вершины обеих компонент (по свойству 1). Поэтому tout[v] будет больше, чем у всех вершин из C′. Если же v ∈ C′, то вызов Explore(v) обойдет все вершины C′, но до C дело еще не дойдет — и максимальное tout-значение в C тоже будет больше.

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

Таким образом, мы научились находить компоненту-исток и вершину в ней. Как найти все вершины только данной компоненты? Рассмотрим обращенный граф G^R, получаемый из G изменением направлений всех ребер (см. рис. 2). В G^R будут те же компоненты сильной связности, как и у G (покажите). Также, найденная вершина компоненты-истока G будет вершиной компоненты-стока графа G^R. Тогда вызов Explore из найденной вершины на графе G^R обойдет только вершины компоненты истока графа G.

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

Заметим, что явно удалять вершины не нужно. Достаточно просто обойти вершины в порядке убывания tout и вызвать Explore из каждой непосещённой.

Итак, мы построили следующий алгоритм выделения компонент сильной связности:

1. Запустить обход в глубину графа G, который вернет вершины в порядке убывания tout. Заметим, что для этого достаточно добавлять вершину в массив при выходе Explore из этой вершины.
2. Построить обращенный граф G^R. Запустить процедуру Explore из каждой непосещённой вершины в порядке убывания tout-значений. Каждое множество вершин, достигнутое в результате очередного запуска обхода, и будет очередной компонентой сильной связности.

Данный алгоритм не просто находит все компоненты связности, но и строит ациклический граф конденсации в порядке топологической сортировки компонент.

Задача A. Конденсация графа ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

6 7
1 2
2 3
3 1
4 5
5 6
6 4
2 4

2
1 1 1 2 2 2

Задача B. Рекурсия ≡

Условие

"Чтобы понять рекурсию, надо понять рекурсию"

Фольклор

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

Неформально ее можно определить как использование в описании объекта самого себя. Если речь идет о процедуре, то в процессе исполнении эта процедура напрямую или косвенно (через другие процедуры) вызывает сама себя.

Рекурсия является очень "мощным" методом построения алгоритмов, но таит в себе некоторые опасности. Например, неаккуратно написанная рекурсивная процедура может войти в бесконечную рекурсию, то есть, никогда не закончить свое выполнение (на самом деле, выполнение закончится с переполнением стека).

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

Рассмотрим программу, состоящую из n процедур P₁, P₂, ..., P_n. Пусть для каждой процедуры известны процедуры, которые она может вызывать. Процедура P называется потенциально рекурсивной, если существует такая последовательность процедур Q₀, Q₁, ..., Q_k, что Q₀ = Q_k = P и для i = 1… k−1 процедура Q_i−1 может вызвать процедуру Q_i. В этом случае задача будет заключаться в определении для каждой из заданных процедур, является ли она потенциально рекурсивной.

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

Формат входного файла

Первая строка входного файла содержит целое число n - количество процедур в программе.

Далее следуют n блоков, описывающих процедуры. Блоки отделены друг от друга и от первой строки входного файла строками, каждая из которых содержит по 5 символов "*" (ASCII 42).

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

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

Формат выходного файла

Для каждой процедуры, присутствующей во входном файле, необходимо вывести слово YES, если она является потенциально рекурсивной, и слово NO — в противном случае.

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

Ограничения

1 ≤ n ≤ 100

Идентификатор процедуры состоит только из маленьких букв латинского алфавита и цифр. Также идентификатор не пуст, и его длина не превосходит 100 символов.

k ≤ n

Примеры тестов

3
p1
2
p1
p2
*****
p2
1 
p1
*****
p3
1
p1

p1: YES
p2: YES
p3: NO

Задача C. Магические порталы ≡

Условие

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

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

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

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

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

Для получения этой информации король планирует запросить в министерстве транспорта соответствующий отчет. Король может запросить либо частичный, либо полный отчет. Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1, для полного отчета L = 1.

Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B, для которых выполняются следующие условия:

• исходно магический портал позволяет перемещаться напрямую из города A в город B;
• если изменить направление перемещения этого магического портала на противоположное, чтобы он позволял напрямую перемещаться из города B в город A, то количество совершенных городов в королевстве станет равным m.

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

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

Пояснения к примерам

В приведенных примерах изначально совершенным является только город 2.

Изменив направление порталов, соединяющих пары городов (2, 3), (2, 4) или (2, 5), можно сделать все города совершенными. Изменение направление любого другого портала делает совершенным один город.

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

В других тестах n ≠ 5.

Система оценивания и описание подзадач

В этой задаче четыре подзадачи. Баллы за каждую подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 1 (20 баллов)

2 ≤ n ≤ 50, p = 0

Подзадача 2 (30 баллов)

2 ≤ n ≤ 300, p = 0

Подзадача 3 (20 баллов)

2 ≤ n ≤ 2000, p = 0

Подзадача 4 (30 баллов)

2 ≤ n ≤ 2000, p = 1

Получение информации о результатах окончательной проверки

По запросу сообщается баллы за каждую подзадачу.

Формат входного файла

Первая строка входного файла содержит два целых числа: n — количество городов в королевстве и p, равное либо 0, если требуется вывести частичный отчет, либо 1, если требуется вывести полный отчет.

Последующие n строк содержат по n символов, каждый из которых может быть «+», «–» или «.», и i-я из этих строк описывает магические порталы, соединяющие i-й город с другими городами.

В i-й строке j-й символ равен «+», если магический портал позволяет напрямую перемещаться из i-го города в j-й, равен «–», если магический портал позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.

Формат выходного файла

Первая строка выходного файла должна содержать одно целое число k — количество совершенных городов в королевстве.

Если требуется частичный отчет (p = 0), то вторая строка выходного файла должна содержать (n−k) целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным (k + i). Если при этом k = n, то вторая строка может отсутствовать, либо быть пустой.

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

Ограничения

2 ≤ n ≤ 2000

Примеры тестов

5 0
.-+++
+.+++
--.+-
---.+
--+-.

1
0 0 0 3

5 1
.-+++
+.+++
--.+-
---.+
--+-.

1
7 0 0 0 3

Задача D. Перестройка ≡

Условие

В некоторой стране было ровно N городов и M дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:

• между любыми двумя городами не больше одной дороги;
• никакая дорога не соединяет город с самим собой.

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

• разрушить одну из существующих дорог;
• построить новую дорогу, которой раньше не было, не ведущую из города в него же.

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

Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.

Формат входного файла

Первая строка содержит два целых числа N и M. Следующие M строк содержат два числа a_i, b_i  — номера городов, которые соединяет i-я дорога.

Формат выходного файла

Выведите одно целое число  — количество способов провести реформу.

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ M ≤ 2 ⋅ 10⁵

1 ≤ a_i, b_i ≤ N, a_i ≠ b_i

Problem E. Biconnectivity ≡

Statement

Input file format

Output file format

Constraints

Sample tests

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

1 1

Задача F. Размещение данных ≡

Условие

Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до n. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.

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

На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2  — с сервера 4, при недоступности канала между серверами 2 и 3  — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.

Рис. 1. Пример сети и отказоустойчивого множества серверов.

В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число 10⁹ + 7.

Требуется написать программу, которая по заданному описанию сети определяет следующие числа: k  — минимальное количество серверов в отказоустойчивом множестве серверов, c  — остаток от деления количества способов выбора отказоустойчивого множества из k серверов на число 10⁹ + 7

Формат входного файла

Первая строка входного файла содержит целые числа n и m  — количество серверов и количество каналов связи соответственно.

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

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

Формат выходного файла

Выведите два целых числа, разделенных пробелом: k  — минимальное число серверов в отказоустойчивом множестве серверов, c  — количество способов выбора отказоустойчивого множества из k серверов, взятое по модулю 10⁹ + 7

Ограничения

2 ≤ n ≤ 200000, 1 ≤ m ≤ 200000

Система оценки и описание подзадач

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

Описание подзадач и системы оценивания

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

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

В приведённом примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.

Примеры тестов

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

2 3

Задача G. Выбор вершин взвешенного дерева ≡

Условие

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

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

Формат входного файла

Граф в этой задаче задан в виде корневого дерева. В графе выделена вершина — корень дерева. Для каждой вершины i, не являющейся корнем, задан номер вершины-предка p_i в корневом дереве. Дерево, заданное таким образом, состоит из рёбер i — p_i для всех вершин i, кроме корня.

В первой строке входного файла записано целое число n  — количество вершин в графе . В следующих n строках задан граф. В i-й из этих строк записаны через пробел два целых числа p_i и q_i; здесь p_i  — номер вершины-предка i-ой вершины, а q_i  — число, записанное в этой вершине. Для корня дерева p_i = 0; для всех остальных вершин 1 ≤ p_i ≤ n.

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

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 100

1 ≤ p_i ≤ n

|q_i| ≤ 10⁴

Примеры тестов

5
0 1
1 2
1 3
2 4
3 5

10

6
5 8
6 0
5 -1
1 1
0 3
1 2

8

Задача H. Простые пути в дереве ≡

Условие

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

Формат входного файла

На первой строке целое число n. Следующие n−1 строка содержат пары чисел от 1 до n  — ребра графа.

Формат выходного файла

n−1 строка. i-я строка должна содержать целое число  — ответ для i-го ребра.

Ограничения

2 ≤ n ≤ 300000

Примеры тестов

5
1 2
2 3
2 4
5 1

13
8
8
9