Question

Имя входного файла: 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). Гарантируется, что каждый конец провода связан напрямую только с одним узлом или другим концом провода. Связь между двумя узлами подразумевает под собой то, что между этими узлами проходит один или несколько проводов. Формат выходных данных В выходной файл нужно вывести одно целое число – минимальное количество проверок, которое нужно сделать Коле.

Answer 1

Надо определять по цвету, провода разных цветов, и разъёмы тоже