Задача A. Быстрое двудольное паросочетание ≡

Условие

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

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

Входной файл содержит целые числа p, q, m — мощности левой правой доли, а также количество рёбер соответственно.

Далее содержится описание m ребер в виде списка пар целых чисел (u_i, v_i). Наличие пары (u_i, v_i) означает ребро между u_i-ой вершиной левой доли и v_i-ой вершиной правой доли.

Гарантируется, кратных рёбер в графе нет.

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

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

Ограничения

1 ≤ p, q ≤ 10⁵

1 ≤ m ≤ 2 * 10⁵

1 ≤ u_i ≤ p

1 ≤ v_i ≤ q

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

3 3 6
1 1
1 2
2 1
2 2
2 3
3 2

3
1 1
2 3
3 2

Задача B. Min-cost-max-flow aka В поисках невест ≡

Условие

Однажды король Флатландии решил отправить k своих сыновей на поиски невест. Всем известно, что во Флатландии n городов, некоторые из которых соединены дорогами. Король живет в столице, которая имеет номер 1, а город с номером n знаменит своими невестами.

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

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

В первой строке входного файла находятся числа n, m и k — количество городов и дорог во Флатландии и сыновей короля, соответственно (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ k ≤ 100). Следующие m строк содержат по три целых положительных числа каждая — города, которые соединяет соответствующая дорога и время, которое требуется для ее прохождения (время не превышает 10⁶). По дороге можно перемещаться в любом из двух направлений, два города могут быть соединены несколькими дорогами.

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

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

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

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

3.00000
3 1 5 6
3 2 7 8

Problem C. Knuth-Morris-Pratt ≡

Statement

Input file format

Output file format

Constraints

Sample tests

yezhiki nachinayut i vyygryvayut
yut

16

Задача D. Длинный текст и много слов (revisited) ≡

Условие

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

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

Ограничения

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

longlongstring
2
short
string

0 1