BerSoft — крупнейшая IT-корпорация в Берляндии. В компании BerSoft работает \(n\) сотрудников, пронумерованных от \(1\) до \(n\).
Первый сотрудник является руководителем компании и у него нет начальника. У каждого другого сотрудника \(i\) есть ровно один непосредственный начальник \(p_i\).
Сотрудник \(x\) считается начальником (непосредственным или косвенным) сотрудника \(y\), если выполняется одно из следующих условий:
- сотрудник \(x\) является непосредственным начальником сотрудника \(y\);
- сотрудник \(x\) является начальником непосредственного начальника сотрудника \(y\).
Структура BerSoft организована таким образом, что руководитель компании является начальником для каждого сотрудника.
Скоро будет проведено соревнование по программированию. Для этой цели будут созданы команды из двух человек. Однако, если в команде один сотрудник является начальником другого, им будет некомфортно вместе. Поэтому команды из двух человек должны быть созданы таким образом, что никто не был начальником для другого. Обратите внимание, что никакой сотрудник не может участвовать более чем в одной команде.
Ваша задача — посчитать максимально возможное количество команд в соответствии с вышеописанными правилами.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможное количество команд в соответствии с вышеописанными правилами.
Примечание
В первом примере можно создать команду \((3, 4)\).
Во втором примере команда не может быть создана, потому что здесь всего \(2\) сотрудника и один является начальником другого.
В третьем примере можно создать команду \((2, 3)\).
В четвертом примере можно создать команды \((2, 4)\), \((3, 5)\) и \((6, 7)\).
В пятом примере можно создать команды \((2, 3)\), \((6, 4)\) и \((5, 7)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
1 2 1
2
1
5
5 5 5 1
7
1 2 1 1 3 3
7
1 1 3 2 2 4
7
1 2 1 1 1 3
|
1
0
1
3
3
3
|