Задача A. Красная Шапочка ≡

Условие

В непроходимом лесу имеется N полянок и M тропинок между ними. Каждая тропинка соединяет две различные полянки. Две полянки могут быть соединены несколькими тропинками.

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

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

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

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

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

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

Первая строка входного файла содержит числа N, M и K (2 ≤ N ≤ 2 000, 1 ≤ M ≤ 100 000, 1 ≤ K ≤ 100 000). Следующие M строк содержат по три числа: B_i, E_i — номера полянок, которые соединяет i-я тропинка, и T_i — минимальное время, за которое Красная Шапочка может по ней пройти (1 ≤ T_i ≤ 10 000).

В следующих K строках находится последовательное описание пути Волка, по два числа в строке: P_i — номер тропинки, по которой он побежит, и V_i — время, которое он на это затратит (1 ≤ V_i ≤ 10 000). Путь волка всегда начинается на полянке 1 и заканчивается на полянке N.

Все числа во входном файле целые и в пределах одной строки разделены пробелами.

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

В том случае, если Красная Шапочка не может добраться до домика бабушки быстрее Волка, выходной файл должен содержать слово NO.

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

Информацию о времени прохождения по тропинкам и остановках на полянках в выходной файл выводить не нужно.

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

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

YES
2
1 4

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

NO

Задача B. Киноакадемия ≡

Условие

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

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

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

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

В первой строке входного файла задано целое число n — количество кинофильмов, участвующих в финале конкурса Киноакадемии. В следующих n строках содержатся по три целых числа a_i, b_i, c_i — уровень ликования, если i-й фильм не выиграет ни в одной из номинаций, уровень ликования, если этот фильм выиграет в номинации на лучшую режиссуру, и уровень ликования, если этот фильм выиграет в номинации на лучший сценарий.

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

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

Ограничения

2 ≤ n ≤ 10⁵ 1 ≤ a_i, b_i, c_i ≤ 10⁹

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

3
3 6 9
1 5 7
1 3 9

17
2 3

Задача C. Автомат с игрушками ≡

Условие

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

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

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

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

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

В первом примере первая монета пройдет лабиринт, и игрок получит игрушки из вершин 1, 3 и 4. Вторая монета пройдет лабиринт, и игрок получит игрушки из вершин 2 и 6. Третья монета пройдет лабиринт, и игрок получит игрушки из вершин 5 и 7.

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

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

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

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

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

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

Выходной файл должен содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле v. Если получить выбранную игрушку невозможно, выведите число~−1.

Ограничения

1 ≤ n ≤ 10⁵ 1 ≤ u_k, w_k ≤ 10⁹

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

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

3

4
0 0 2 1
4 1 3 1
0 0 0 0
0 0 0 0
3

-1