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

1272. Метро не в Екатеринбурге

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В небольшом городке началось строительство метрополитена. Особенностью городка является то, что он стоит на маленьких островах, некоторые из которых соединены тоннелями или мостами. По убеждению мэра, метро должно быть проложено под землей, поэтому в проекте строительства должно использоваться как можно меньше мостов. Единственное требование, которое предъявляется к метрополитену, заключается в том, чтобы жители города могли добраться на метро (возможно, с пересадками) с любого острова на любой другой. К счастью, известно, что мостов и тоннелей для этого достаточно. Из соображений экономии было решено построить как можно меньше переездов между островами.
Ваша задача: зная план города, определить минимально возможное количество мостов, которые необходимо задействовать при строительстве метрополитена.

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

В первой строке через пробел записаны три целых числа N (количество островов, 1 ≤ N ≤ 10000), K (количество тоннелей, 0 ≤ K ≤ 12000) и M (количество мостов, 0 ≤ M ≤ 12000). Затем следуют K строк, в каждой из которых записаны два числа — номера островов, соединённых соответствующим тоннелем. Последние M строк описывают мосты в аналогичном формате.

Результат

должен содержать единственное число — минимальное число мостов, которые необходимо задействовать при строительстве метрополитена.

Пример

исходные данныерезультат
6 3 4
1 2
2 3
4 5
1 3
3 4
4 6
5 6
2
Автор задачи: Магаз Асанов (подготовил — Игорь Гольдберг)
Источник задачи: Чемпионат Уральского государственного университета, 25 октября 2003 года