Задача I. Преображение
Задачу добавил: alef
Успешно сдано решений: 16
Время на тест 2 с, память 256 Мб
В ходе совместной работы Кеша познакомился с коллективом НИИ поближе. И понял, что он очень часто слышал от сотрудников такие истории:
«Вообще-то я закончил физический факультет. Но так получилось, что мне нужно было выполнить очень сложные расчеты. Пришлось освоить ремесло программиста. Потом, когда я уже работал программистом, передо мной встала интересная задача, связанная с генетическими алгоритмами. К сожалению, коллеги-биологи не могли хорошо формулировать требования, и пришлось самому изучать предметную область. Изучил, да так, что стал специализироваться в биологии. Дело интересное, но, чтобы поставить нужные биологические эксперименты, требовались познания в химии. Так вот и пришлось переквалифицироваться в химики.»
«Учился я на биолога. Хорошо, в общем, учился. Но когда работать стал, понял — мне куда интереснее все организовывать, чем непосредственно заниматься биологическими задачами. А других — хозяйственных — задач ой как хватало. Нужно найти, где можно приобрести прибор, образцы, реактивы... Начал с бухгалтерских курсов, а потом получил экономическое образование. А потом стал по служебной лестнице двигаться. Но чем выше, тем больше еще и юридические знания нужны. Так что юрист я теперь. Ну да это ничего, у нас один экономист вспомнил, что очень любил в вузе математику, такие расчетные схемы строит!»
«Я по образованию химик. Но столько времени уходило на добывание реактивов, что стал задумываться, нет ли других способов достичь тех же эффектов. Оказалось, есть. Лазерами вот заинтересовался. Диссертацию по лазерной физике, кстати, в прошлом году защитил».
Однажды Кеша задумался — ведь сколько люди переучивались, тратили время, силы... А в итоге, например, физик стал химиком, а химик стал физиком. Возможно, им и не нужно было переучиваться? Ведь набор (физик, биолог, химик) превратился в (химик, юрист, физик). А для этого было бы достаточно переучиться только одному биологу.
Кеша хочет понять, какое наименьшее количество сотрудников всё-таки нужно было переучить, чтобы получить необходимое для НИИ множество профессий. Это множество, разумеется, совпадает с множеством профессий, полученных всеми сотрудниками после переучивания. Помогите Кеше решить эту задачу.
Для простоты
каждая профессия кодируется некоторым
числом.
Каждый сотрудник может быть либо переучен в
точности так, как он был переучен, либо не переучен вообще.
Формат входного файла input.txt
Первая строка — целое число N — количество сотрудников НИИ (1 ≤ N ≤ 105).
Каждая из следующих N строк содержит пару целых положительных чисел, не превосходящих 109, записанных через пробел, — номер изначальной профессии и профессии после переучивания очередного сотрудника. Гарантируется, что как все изначальные профессии сотрудников, так и все профессии сотрудников после переучивания различны.
Формат выходного файла output.txt
Первая строка — целое число — количество человек, которое минимально требуется переучить, чтобы получить окончательное состояние трудового коллектива НИИ.
Пример входного файла
3
1 4
2 3
4 1
Пример выходного файла
1