Задача A. Ожерелье ≡

Условие

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

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

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 50).

Во второй строке через пробел следуют N различных чисел от 1 до N — номера колечек, расположенных вдоль нити по часовой стрелке.

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

Выходной файл должен содержать описание процесса упорядочения.

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

Количество строк выходного файла не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести одно число –1.

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

4
3 2 4 1

1 3
2 4
1 4
0

Задача B. Менеджер памяти ≡

Условие

Пете поручили написать менеджер памяти для новой стандартной библиотеки языка H++. В распоряжении у менеджера находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера — обрабатывать запросы приложений на выделение и освобождение памяти.

Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется.

Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T — запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется.

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

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

Первая строка входного файла содержит числа N и M — количество ячеек памяти и количество запросов соответственно (1 ≤ N ≤ 2³¹ − 1; 1 ≤ M ≤ 10⁵). Каждая из следующих M строк содержит по одному числу: (i + 1)-я строка входного файла (1 ≤ i ≤ M) содержит либо положительное число K, если i-й запрос — запрос на выделение с параметром K (1 ≤ K ≤ N), либо отрицательное число  − T, если i-й запрос — запрос на освобождение с параметром T (1 ≤ T < i).

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

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

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

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

1
3
-1
-1
1
-1

Задача C. Казино ≡

Условие

Вновь открытое казино предложило оригинальную игру.

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

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому — на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.

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

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

В первой строке входного файла записано число K (1 ≤ K ≤ 26) — количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) — цена фишки соответствующего цвета.

В (K + 2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задается L строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

В следующей строке содержится число N (1 ≤ N ≤ 150) — количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.

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

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

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

6
a 1
b 4
d 2
x 3
f 1
e 3
fxeeabadd
2
aba
ed

16

Задача D. Красивые числа ≡

Условие

Саша считает красивыми числа, десятичная запись которых не содержит других цифр, кроме 0 и k (1 ≤ k ≤ 9). Например, если k = 2, то такими числами будут 2, 20, 22, 2002 и т.п. Остальные числа Саше не нравятся, поэтому он представляет их в виде суммы красивых чисел. Например, если k = 3, то число 69 можно представить так: 69 = 33 + 30 + 3 + 3.

Однако, не любое натуральное число можно разложить в сумму красивых целых чисел. Например, при k = 5 число 6 нельзя представить в таком виде. Но если использовать красивые десятичные дроби, то это можно сделать: 6 = 5.5 + 0.5.

Недавно Саша изучил периодические десятичные дроби и начал использовать и их в качестве слагаемых. Например, если k = 3, то число 43 можно разложить так: 43 = 33.(3) + 3.(3) + 3 + 3.(3).

Оказывается, любое натуральное число можно представить в виде суммы положительных красивых чисел. Но такое разложение не единственно — например, число 69 можно также представить и как 69 = 33 + 33 + 3. Сашу заинтересовало, какое минимальное количество слагаемых требуется для представления числа n в виде суммы красивых чисел.

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

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

Во входном файле записаны два натуральных числа n и k (1 ≤ n ≤ 10⁹; 1 ≤ k ≤ 9).

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

В выходной файл выведите разложение числа n в сумму положительных чисел, содержащих только цифры 0 и k, количество слагаемых в котором минимально. Разложение должно быть представлено в виде: n = a₁ + a₂ + …  + a_m

Слагаемые a₁, a₂, …, a_m должны быть выведены без ведущих нулей, без лишних нулей в конце дробной части. Запись каждого слагаемого должна быть такой, что длины периода и предпериода дробной части имеют минимально возможную длину. Например, неправильно выведены числа: 07.7; 2.20; 55.5(5); 0.(66); 7.(0); 7. ; .5; 0.33(03). Их следует выводить так: 7.7; 2.2; 55.(5); 0.(6); 7; 7; 0.5; 0.3(30).

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

Выходной файл не должен содержать пробелов.

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

69 3

69=33+33+3

6 5

6=5.5+0.5

10 9

10=9.(9)

Задача E. Сетевая игра ≡

Условие

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

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

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

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

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

В первой строке входного файла задано число N (1 ≤ N ≤ 50) — количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк входного файла содержат по две пары целых чисел — координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.

Координаты всех точек неотрицательны и не превосходят 50.

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

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

Максимальная оценка за решение задачи при N ≤ 13 равна 40 баллам.

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

11
1 1 1 2
2 3 2 4
3 1 3 2
1 2 1 3
1 1 2 1
2 1 2 2
2 1 3 1
1 2 2 2
2 2 3 2
1 3 2 3
2 3 3 3

1
6

Задача F. Сталкер ≡

Условие

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

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

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

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

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

В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад — в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i — количество дорог, обозначенных на i-ой карте. Затем идут r_i строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 3 × 10⁵ (r₁ + r₂ + …  + r_K ≤ 3 × 10⁵).

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

В выходной файл необходимо вывести одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1. В выходной файл необходимо вывести одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.

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

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

2

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

-1

Задача G. Праздники ≡

Условие

На планете в звездной системе Альфа Кентавра неделя состоит из A дней, а год — из B дней. Годы нумеруются последовательными натуральными числами: 1, 2, 3, … Кроме того, годы с номерами C₁, C₂, …, C_N являются високосными и состоят из (B + 1) дней. В году дни с номерами D₁, D₂, …, D_M являются праздничными. Если праздник попадает на (B + 1)-й день года, то он отмечается только в високосные годы. Первый день первого года является первым днем недели.

Один из жителей планеты решил устроиться на новую работу. В соответствии с заключенным трудовым договором он будет числиться на данной работе в течение E дней, начиная с первого дня 1-го года. По договору он имеет право выбрать один день недели (с 1 по A), который будет для него выходным. Праздничные дни также считаются нерабочими. Житель хочет выбрать себе выходной день таким образом, чтобы за период действия договора у него было максимальное количество нерабочих дней.

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

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

В первой строке входного файла через пробел записаны числа A и B — количество дней в неделе и в невисокосном году соответственно (1 ≤ A ≤ 2500, 1 ≤ B ≤ 10000). Во второй строке записано число N — количество високосных лет, и в третьей — номера C₁, C₂, …, C_N високосных лет в возрастающем порядке (0 ≤ N ≤ 5000, 1 ≤ C₁ < C₂ < …  < C_N ≤ 10⁷). В следующей строке число M — количество праздничных дней в году, и на новой строке — D₁, D₂, …, D_M в возрастающем порядке (1 ≤ D₁ < D₂ < …  < D_M ≤ B + 1). В последней строке записано число E (1 ≤ E ≤ 10⁹). Известно, что житель заключил контракт не более чем на 10⁷ лет.

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

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

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

7 13
1
2
2
1 14
29

1 8

3 9
0

3
1 4 7
19

2 13

Задача H. Опечатки ≡

Условие

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

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

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

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

В первой строке входного файла через пробел записаны натуральные числа% N ≥ 1 — общее количество слов в словаре и M ≥ 1 — количество слов в проверяемом тексте (N + M ≤ 20 000) В последующих N строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют M строк, в которых записаны слова проверяемого текста, по одному слову в строке.

Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.

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

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

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

5 8
father
and
or
mother
a
Father 
and 
mather 
go 
o
for 
e 
walk

Father 1 father
and 1 and
mather 2
go 1 or
o 2
for 1 or
e 1 a
walk 0

Задача I. Горнолыжные соревнования ≡

Условие

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

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

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

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

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

В первой строке входного файла задано число N — количество ворот на трассе (0 ≤ N ≤ 500), в~следующих двух строках заданы S_x, S_y, F_x, F_y — координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа a_i, b_i, y_i, c_i — x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (a_i < b_i, F_y < y_i < S_y, c_i — целое число, 0 ≤ c_i ≤ 10000). Все координаты — целые числа, не превосходящие по модулю 10000.

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

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

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

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

7.8126

Задача J. Pinball ≡

Условие

Поле в Pinball представляет собой прямоугольник без стенок, состоящий из n × m квадратных клеток, (n клеток по вертикали, m клеток по горизонтали). Клетки по вертикали нумеруются сверху вниз, по горизонтали — слева направо. В каждой клетке можно установить одну отражающую пластинку в одном из двух положений: в положении 1 — от левого верхнего угла к правому нижнему или в положении 2 — от левого нижнего к правому верхнему. Летящий шарик при столкновении с пластинкой изменяет свою траекторию, при этом угол падения шарика всегда равен углу отражения и составляет 45 градусов (см. рисунок).

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

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

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

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

Первая строка входного файла содержит три числа: n, m (1 ≤ n, m ≤ 1000) и k, где k — общее количество пластинок, которые были исходно расставлены.

Во второй строке указываются номера клетки по вертикали и по горизонтали, на границе которой лежит точка A, и номер стороны, на которой она находится. Стороны клетки пронумерованы целыми числами от 1 до 4, при этом верхней стороне присвоен номер 1, далее по часовой стрелке нумеруются остальные стороны.

Третья строка содержит описание точки B в том же формате.

Следующие k − 1 строк описывают пластинки, оставшиеся на поле. В каждой строке записаны по три числа: первое — номер клетки по вертикали, второе — номер клетки по горизонтали, третье — положение пластинки в клетке (число 1 или 2).

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

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

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

5 2 1

Задача K. Великолепный Гоша ≡

Условие

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

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

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

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

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

В первой строке входного файла задано число N (4 ≤ N ≤ 1 000) — количество домов на схеме.

Во второй строке записано число M (2 ≤ M ≤ 20 000)  — количество кабелей в схеме.

В следующих M строках расположены пары номеров домов, соединенных кабелями на схеме. Дома имеют номера от 1 до N.

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

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

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

Каждая операция описывается начальным и конечным положением кабелей. Сначала четырьмя целыми числами V₁, V₂, V₃, V₄ записывается исходное положение кабелей, при этом один из кабелей соединяет дома с номерами V₁, V₂, а другой — V₃, V₄. Затем в таком же формате описывается конечное положение.

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

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

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

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

Условие

В непроходимом лесу имеется 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