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

Условие

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

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

Входной файл содержит целые числа 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