Обход в глубину

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

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

В результате небольшого исследования Иванушка установил, между какими компаниями существует взаимное доверие (причем всегда если компания доверяет компании B, то компания B доверяет компании A).

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

Напишите программу, которая определит, какое максимальное число компаний может объединить Иванушка под своим началом.

Будем считать, что Иванушка — честный предприниматель и он никогда не подтасовывает рассылаемые им списки.

Входные данные
В первой строке входных данных содержится число N — количество фирм (1≤N≤2000). Далее идут N чисел, описывающих ответ фирмы на первое предложение Иванушки (1 — согласие, 0 — отказ). Далее задается число M (0≤M≤200000) — количество пар компаний, между которыми существует доверие. Далее следуют M пар чисел, задающих номера фирм, между которыми существует взаимное доверие (числа в паре не могут быть одинаковыми). Любая пара компаний упоминается в этом списке не более одного раза.

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

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

Под будущей магистралью залегают \(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 станций и M соединяющих их перегонов. Любые две станции соединены не более чем одним перегоном. Сеть перегонов устроена так, что, отправившись от любой станции, можно вернуться на нее, только проехав хотя бы один перегон дважды. На железной дороге организовано движение электричек. Каждая электричка ходит в обоих направлениях по своему маршруту между двумя конечными станциями и останавливается на всех промежуточных станциях

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

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

	4 станции, 3 перегона: 1-4, 2-4, 3-4 Маршруты: 1-4-2, 2-4-3, 3-4-1.   Ответ: решения нет
	5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5 Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.   Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5 тарифный номер: 1 4 1 5 3   Замечание: тарифные номера разных станций могут совпадать.

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

В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

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

В первую строку выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Если существует несколько решений, необходимо вывести любое из них.

В развлекательном центре Е-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть \(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\) — минимальную возможную энергию, которая потребуется архимагу для путешествия.

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

Примеры

5 4
1 3
1 2
2 3
2 4

4
4
3
4
1

Примеры

4
11 10 11 11
1 2
2 3
2 4

Примеры

Примеры