Задача №114044. Экспедиция
Планируется отправить экспедицию к соседней звёздной системе. Были отобраны \(n\) кандидатов, пронумерованных от \(1\) до \(n\), среди которых необходимо выбрать участников экспедиции. Организаторы хотят отправить в экспедицию как можно больше кандидатов.
Среди кандидатов был проведён опрос, в процессе которого каждый мог указать не более, чем одного из остальных кандидатов, с которым он не готов отправиться в экспедицию. Результатом опроса для \(i\)-го кандидата является целое число \(a_i\), которое равно номеру кандидата, с которым \(i\)-й кандидат не готов отправиться в экспедицию, либо \(-1\), если \(i\)-й кандидат готов отправиться в экспедицию в любом составе.
Теперь организаторы должны выбрать, кто из кандидатов отправится в экспедицию. Решено было выбрать участников экспедиции так, что если туда входит некоторый кандидат \(i\), и \(a_i \ne -1\), то туда не входит кандидат \(a_i\). Организаторы хотят выбрать максимальное количество участников экспедиции.
Требуется написать программу, которая по заданным результатам опроса кандидатов определяет максимальное количество кандидатов, которых можно отправить в экспедицию.
В первой строке входных данных находится целое число \(n\) — количество кандидатов (\(1 \le n \le 300\,000\)).
В следующих \(n\) строках даны результаты опроса, \(i\)-я из этих строк содержит результат опроса \(i\)-го кандидата, целое число \(a_i\) (\(a_i = -1\) или \(1 \le a_i \le n\), \(a_i \neq i\)).
В единственной строке выведите одно целое число — максимальное количество кандидатов, которых можно отправить в экспедицию.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
4 2 4 2 1
2
3 2 -1 2
2