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

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ p, q ≤ 105

1 ≤ m ≤ 2*105

1 ≤ ui ≤ p

1 ≤ vi ≤ q

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 6
1 1
1 2
2 1
2 2
2 3
3 2
3
1 1
2 3
3 2

0.033s 0.008s 15