ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1109. Конференция

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
На предстоящую конференцию было послано M представителей страны A и N представителей страны B (MN ≤ 1000). Представителям сопоставлены номера 1, 2, …, M для страны A и 1, 2, …, N для страны B. Перед конференцией было выбрано K пар представителей. Каждая такая пара состоит из одного члена делегации A и одного члена делегации B. Если существует пара, в которую включены член №i делегации A и член №j делегации B, то №i и №j могут вести переговоры. Каждый посетитель конференции был включён хотя бы в одну пару. Директор конгресс-центра хочет провести прямые телефонные соединения между комнатами делегатов так, что каждый будет соединён хотя бы с одним представителем другой делегации, и каждое соединение пролегает между людьми, которые могут вести переговоры. Директор также хочет минимизировать количество телефонных соединений. Напишите программу, которая по M, N, K и K парам представителей находит минимальное число необходимых соединений.

Исходные данные

Первая строка ввода содержит M, N и K. Следующие K строк описывают выбранные пары в виде двух целых чисел p1 и p2, где p1 — член делегации A, а p2 — член делегации B.

Результат

Вывод должен содержать минимальное количество необходимых телефонных соединений.

Пример

исходные данныерезультат
3 2 4
1 1
2 1
3 1
3 2
3
Источник задачи: Bulgarian National Olympiad Day #1