"Поздравление с Новым Годом" (поиск наилучшего решения)

[Legioner93]

Поздравление с Новым Годом

Time limit = 1 секунд(ы)
Петя хочет поздравить своих друзей с новым годом. У него есть N открыток и K конвертов. Некоторые открытки не помещаются в некоторые конверты. Петя хочет поздравить максимальное количество друей (а их у него очень-очень много). Но он совсем не умеет программировать. Помогите ему — напишите программу, которая определяет, в какие конверты какие открытки класть, чтобы поздравить максимальное количество друзей.

Вход: В первой строчке находятся натуральные числа N, K, C, разделенные пробелами. За ними следует C пар чисел. Открытку номер A можно поместить в конверт номер B только тогда, когда во входе есть пара (A, B).

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

Если есть несколько решений, представьте одно из них.

Ограничения: 0 ≤ N, K ≤ 1000, 0 ≤ C ≤ 12000.

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

Некоторые (очевидные) мысли по поводу задачи. 1) Если в какой-то конверт вообще можно поместить только одну открытку, то её следует туда поместить "намертво", вне зависимости от остальных данных. Тогда эта открытка в последующем переборе уже не участвует. 2) Если на данном наборе в итоге получилось, что конверт остался пустой, но в него возможно поместить некоторые открытки, то можно поместить в него какую-нибудь их этих открыток, предварительно вытащив её из своего конверта. "Ущерба" набору не будет.
Но более или менее эффективный алгоритм мне составить не удалось. Буду благодарен любой помощи и наводкам! Мне кажется, задача довольно общая (есть два множества, между некоторыми элементами первого и второго множества возможна связь. Какое максимальное кол-во связей возможно одновременно при сохранении взаимной однозначности?), так что алгоритм по-любому быть должен. Спасибо!

[venco]

Используйте bipartite matching алгоритм, например Hopcroft–Karp. См. Википедию.

[Zealint]

А зачем такой сложный алгоритм сразу? Можно обычный, на основе dfs, за $O(mn)$, например, отсюда. Хотя если с головой делать, он еще вдвое короче будет.

[venco]

Согласен, это я погорячился.

[Legioner93]

Спасибо, постараюсь!