Задача A. Силовые поля ≡

Условие

В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.

Экспериментальная установка содержит квадратную платформу размером 10⁹ × 10⁹, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.

Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (x_i, y_i).

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

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

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

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

Последующие n строк содержат по два целых числа x_i, y_i — координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.

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

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

Ограничения

1 ≤ k ≤ n ≤ 200 000, 1 ≤ x_i, y_i ≤ 10⁹

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

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

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

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

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

На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.

Рис 1. Силовые поля в примере описания входных данных.

Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.

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

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

9

Задача B. Повышение квалификации ≡

Условие

Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают n сотрудников. Каждому сотруднику присвоен уникальный номер от 1 до n, директору присвоен номер 1. У каждого сотрудника, кроме директора, есть ровно один непосредственный начальник. Непосредственный начальник сотрудника i имеет номер p_i , причем p_i < i.

Сотрудник x является подчиненным уровня 1 сотрудника y, если p_x = y. Для k > 1 сотрудник x является подчиненным уровня k сотрудника y, если сотрудник p_x является подчиненным уровня k − 1 сотрудника y.

У директора компании появилась возможность направить некоторых сотрудников на курсы повышения квалификации. Для этого он решил выбрать два числа L и R и направить на курсы всех сотрудников с номерами i, такими что L ≤ i ≤ R.

Перед тем, как выбрать числа L и R, директор получил m пожеланий от сотрудников компании, j-е пожелание задается двумя числами u_j и k_j и означает, что сотрудник u_j просит отправить на курсы одного из своих подчиненных уровня k_j. Для экономии средств директор хочет выбрать такие L и R, чтобы количество сотрудников, направленных на повышение квалификации, было минимальным возможным, но при этом все пожелания были выполнены.

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

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

Первая строка входного файла содержит число n — количество сотрудников компании. Вторая строка содержит (n − 1) чисел: p₂, p₃, …, p_n (1 ≤ p_i ≤ i) — номера непосредственных начальников сотрудников.

Третья строка содержит число m — количество пожеланий от сотрудников.

Последующие m строк задают пожелания сотрудников и содержат по два целых числа u_j, k_j (1 ≤ u_j < n, 1 ≤ k_j < n, гарантируется, что у сотрудника u_j есть хотя бы один подчиненный уровня k_j).

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

Необходимо вывести два искомых числа: L и R. Если оптимальных пар (L, R) несколько, требуется вывести ту, в которой значение L минимально.

Ограничения

2 ≤ n, m ≤ 200 000

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

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

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

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

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

На повышение квалификации будут направлены сотрудники с номерами 3, 4, 5 и 6. Сотрудник с номером 3 является подчиненным уровня 1 сотрудника с номером 1, сотрудник с номером 4 — подчиненным уровня 2 сотрудника с номером 1, а сотрудник с номером 6 — подчиненным уровня 1 сотрудника с номером 3.

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

7
1 1 2 2 3 3
3
1 1
3 1
1 2

3 6

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

Условие

Телекоммуникационная сеть крупной 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

Задача D. Полезные ископаемые ≡

Условие

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

Участок поверхности планеты, на котором планируется добывать полезные ископаемые, представляет собой клетчатый прямоугольник размером w на h, клетки участка имеют координаты от (1, 1) до (w, h). В некоторых клетках участка находятся базы специалистов, в которые могут быть доставлены партии роботов. Всего на участке размещено s баз, и i-я база находится в клетке с координатами (x_i, y_i).

Каждая партия роботов характеризуется тремя параметрами: j-я партия доставляется на базу b_j, содержит n_j роботов и каждый робот партии обладает мобильностью m_j.

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

Рис. 1. Возможные перемещения робота в восьми направлениях.

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

Руководством проекта получена информация о t партиях роботов, которые могут быть последовательно отправлены на планету. После доставки всех партий роботов, учитывая их ограниченную мобильность, возможна ситуация, что не удастся разместить роботов на участке так, чтобы в каждой клетке оказалось не больше q роботов. Поэтому руководство должно выбрать k первых партий роботов, где 0 ≤ k ≤ t, которые будут полностью доставлены на соответствующие базы. После этого, если k < t, следует дополнительно принять z из n_k + 1 роботов следующей, (k + 1)-й партии, 0 ≤ z < n_k + 1.

Все полученные таким образом роботы должны с учетом ограничения на мобильность разместиться на участке таким образом, чтобы в каждой клетке было не более q роботов. После этого они будут активированы и начнут добычу полезных ископаемых. Разумеется, руководство проекта старается максимизировать количество роботов, которые будут доставлены на планету, поэтому, с учетом описанных ограничений, требуется максимизировать k, а затем максимизировать z.

Требуется написать программу, которая по размерам участка, числу q, описанию расположения баз, а также количеству запланированных партий роботов и их описанию определяет максимальное число k — количество партий роботов, и затем – максимальное число z – дополнительное количество роботов из (k + 1)-й партии, чтобы, доставив роботов на планету, их можно было разместить на участке таким образом, чтобы в каждой клетке оказалось не более q роботов.

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

Первая строка входного файла содержит числа w, h, s и q. Последующие s строк содержат по два целых числа x_i, y_i и описывают базы специалистов (1 ≤ x_i ≤ w, 1 ≤ y_i ≤ h).

Следующая строка содержит число t — количество партий роботов. Последующие t строк описывают партии роботов и содержат по 3 целых числа: b_j, n_j и m_j (1 ≤ b_j ≤ s, 1 ≤ n_j ≤ w × h × q, 0 ≤ m_j < max(w, h)).

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

Требуется вывести два числа: k и z, 0 ≤ k ≤ t. Если k = t, то z должно быть равно 0, иначе должно выполняться условие 0 ≤ z < n_k + 1.

Ограничения

1 ≤ w, h ≤ 10⁵, 1 ≤ s ≤ 4, 1 ≤ q ≤ 100, 1 ≤ t ≤ 100,

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

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

Рис. 2. Возможное размещение роботов на участке в данном примере.

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

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

Тесты для подзадачи 6 запускаются только в случае, если все тесты подзадач 1–5 успешно пройдены. Каждый тест в подзадаче 6 оценивается независимо в 1 балл.

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

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

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

4 3 2 1
1 1
3 2
3
1 4 1
2 9 1
1 12 2

1 7

Задача E. Интересные числа ≡

Условие

Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 — интересные.

Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от L до R включительно. Это число может оказаться довольно большим для больших L и R, поэтому Софья хочет найти остаток от деления этого числа на 10⁹ + 7.

Требуется написать программу, которая по заданным L и R определяет количество интересных чисел, лежащих в диапазоне от L до R включительно, и выводит остаток от деления этого числа на 10⁹ + 7.

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

Входной файл содержит две строки. Первая строка содержит число L, вторая строка содержит число R.

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

Выходной файл должен одно целое число — остаток от деления количества интересных чисел, лежащих в диапазоне от L до R включительно, на 10⁹ + 7.

Ограничения

1 ≤ L ≤ R ≤ 10¹⁰⁰

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

Подзадача 1 (21 балл)

L = 1, R ≤ 1000.

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

Подзадача 2 (22 балла)

1 ≤ L ≤ R ≤ 10¹⁸.

В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (24 балла)

L = 1, R = 10^k для некоторого целого k, 2 ≤ k ≤ 100.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (33 балла)

1 ≤ L ≤ R ≤ 10¹⁰⁰.

В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

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

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

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

1
100

54

Задача F. Гармоническая последовательность ≡

Условие

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел a₁, a₂, …, a_N гармоничной, если каждое число, кроме a₁ и a_N, равно сумме соседних: a₂ = a₁ + a₃, a₃ = a₂ + a₄, …, a_N − 1 = a_N − 2 + a_N. Например, последовательность [1, 2, 1, −1] является гармоничной, поскольку 2 = 1 + 1, и 1 = 2 + (−1).

Рассмотрим последовательности равной длины: A = [a₁, a₂, …, a_N] и B = [b₁, b₂, …, b_N]. Расстоянием между этими последовательностями будем называть величину N(A, B) = |a₁ − b₁| + |a₂ − b₂| + ⋯ + |a_N − b_N|. Например, d([1, 2, 1, −1], [1, 2, 0, 0]) = |1 − 1| + |2 − 2| + |1 − 0| + |−1 − 0| = 0 + 0 + 1 + 1 = 2.

В конце лекции профессор написал на доске последовательность из N целых чисел B = [b₁, b₂, …, b_N] и попросил студентов в качестве домашнего задания найти гармоничную последовательность A = [a₁, a₂, …, a_N], такую, что d(A, B) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние d(A, B).

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

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

Первая строка входного файла содержит целое число N — количество элементов в последовательности.

Вторая строка содержит n целых чисел b₁, b₂, …, b_N.

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

Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Ограничения

3 ≤ N ≤ 300 000; −10⁹ ≤ b_i ≤ 10⁹

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

В приведенном примере оптимальной является, например, гармоничная последовательность [1, 2, 1, −1].

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

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

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

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

N = 3, −10 ≤ b_i ≤ 10

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

3 ≤ N ≤ 500, −100 ≤ b_i ≤ 100

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

3 ≤ N ≤ 100 000, −100 ≤ b_i ≤ 100

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

3 ≤ N ≤ 1000, −10⁹ ≤ b_i ≤ 10⁹

Подзадача 5 (40 баллов)

3 ≤ N ≤ 300 000, −10⁹ ≤ b_i ≤ 10⁹

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

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

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

4
1 2 0 0

2

Задача G. Странные строки ≡

Условие

Рассмотрим строку S, состоящую из строчных букв латинского алфавита. Примером такой строки является, например, строка «abba».

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

Например, W(«abba») = {«a», «b», «ab», «ba», «bb», «abb», «bba», «abba»}.

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

Например, Y(«abba») = W(«abba») ∪ {«aa», «aba»}. Знак ∪ обозначает объединение множеств.

Будем называть строку S странной, если для нее W(S) = Y(S). Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее W(«abb») = Y(«abb») = {«a», «b», «ab», «bb», «abb»}.

Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке S в качестве подстроки несколько раз. Так, странность строки «abba» равна 7, поскольку любая ее подстрока, кроме всей строки, является странной.

Требуется написать программу, которая по заданной строке S определяет ее странность.

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

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

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

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

Ограничения

Строка S имеет длину от 1 до 200 000 символов.

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

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

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

Строка S состоит только из букв «a» и «b». Длина строки S не превышает 50.

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

Длина строки S не превышает 50.

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

Длина строки S не превышает 1000.

Подзадача 3 (34 балла)

Длина строки S не превышает 200 000.

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

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

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

abba

7

Задача H. Поездка на каникулах ≡

Условие

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

Поезд следует от станции 1 до станции N, делая остановку на каждой станции. В поезде K мест, пронумерованных от 1 до K. На поезд продаются билеты, каждый билет характеризуется тремя числами: S, T и A. Такой билет позволяет проехать от станции S до станции T на месте A.

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

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

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

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

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

Первая строка входного файла содержит числа N, M и K — количество станций, количество уже проданных билетов и количество мест в поезде. Последующие M строк содержат информацию о проданных билетах.

Каждая строка содержит три числа: s_i, t_i и a_i — номер станции, от которой куплен билет, номер станции, до которой куплен билет, и номер места, на которое куплен билет.

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

Далее идет строка, которая содержит число Q. Последующие Q строк содержат описания вариантов поездки. Каждая строка содержит два числа: f_j, d_j — номер станции, от которой Иван хочет поехать в этом варианте, и номер станции, до которой он хочет поехать.

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

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

Ограничения

2 ≤ N ≤ 200 000; 0 ≤ M ≤ 200 000, 1 ≤ K ≤ 200 000

1 ≤ s_i < t_i ≤ N; 1 ≤ a_i ≤ K

1 ≤ Q ≤ 200 000; 1 ≤ f_j < d_j ≤ N

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

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

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

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

N ≤ 100; M ≤ 100; K ≤ 100, Q = 1

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

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q = 1

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

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q ≤ 200 000

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

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

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

На перегоне от 2-й до 3-й станции все места заняты, поэтому проехать от 1-й до 5-й станции невозможно. От 3-й до 5-й станции можно проехать, используя два билета: от 3-й до 4-й станции на место 2 и от 4-й до 5-й на место 1. От 4-й до 5-й станции можно проехать, используя один билет на место 1.

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

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

-1
2
1