<ПРЕД Задача:
СЛЕД>
Задачу решили 623 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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

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 2 3
1 1
1 2
2 1

Выход#1
2
1 2
2 1

Автор:
Описание и тесты -- Евгений Барский.
15 апреля 2004

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID = 3.233.215.196