Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Меломан Коля работает на студии звукозаписи "Dimanovo Records". Недавно состоялось знаме-
нательное событие в жизни студии – она переехала на новое место. Однако переезд был произведен
в достаточно сжатые сроки, и вся аппаратура перевозилась на скорую руку. В результате на пульте
диджея перепутались провода, часть из них переплелась между собой, образуя узлы. Теперь совсем
непонятно какие провода идут между узлами, какой из них ведет к колонкам, какой к микрофону,
какой к ноутбуку и т.д.
Коля задумался, сколько же времени у него займет, чтобы восстановить соответствие прово-
дов входам на пульте. Для каждой проверки он подключает то, или иное устройство к одному из
проводов и пробует им воспользоваться. Если устройство заработало, то провод был подключен
правильно. Все устройства различны, и каждому устройству соответствует лишь один из проводов.
Необходимо посчитать, какое наименьшее количество проверок ему нужно будет сделать, чтобы
гарантированно восстановить нужную конфигурацию проводов.
Формат входных данных
В первой строке входного файла содержится три целых числа N, M, K, где N – количество
проводов, подсоединенных к пульту, M – количество узлов, завязавшихся на проводах, и K – ко-
личество строк, описывающих перепутавшиеся провода (1 ⩽ N ⩽ K ⩽ 100000, 0 ⩽ M ⩽ 100000).
Концы проводов, которые уже подключены к пульту диджея, нумеруются числами от 1 до N, дру-
гие концы проводов нумеруются от N + 1 до 2N. Номера узлов лежат в диапазоне от 2N + 1 до
2N + M.
Следующие K строк содержат описания связей между концами проводов и узлами: i-я строка
содержит два целых числа ai
, bi – номера связанных концов проводов или узлов (1 ⩽ i ⩽ K,
1 ⩽ ai
, bi ⩽ 2N + M). Гарантируется, что каждый конец провода связан напрямую только с одним
узлом или другим концом провода. Связь между двумя узлами подразумевает под собой то, что
между этими узлами проходит один или несколько проводов.
Формат выходных данных
В выходной файл нужно вывести одно целое число – минимальное количество проверок, которое
нужно сделать Коле.
