В компании работает n сотрудников, пронумерованных от 1 до n. У каждого сотрудника либо нет руководителя, либо есть ровно один непосредственный руководитель — некоторый другой сотрудник с другим номером. Сотрудник A называется начальником другого сотрудника B, если выполняется хотя бы одно из двух условий:
- Сотрудник A — непосредственный руководитель сотрудника B.
- У сотрудника B есть непосредственный руководитель, сотрудник C, такой, что A является начальником сотрудника C.
В структуре компании нет циклов. То есть никакой сотрудник не является начальником своего непосредственного руководителя.
Сегодня компания собирается организовать праздник. Для этого необходимо разделить всех n сотрудников на несколько групп: каждый человек должен относиться ровно к одной группе. Более того, в каждой группе не должно быть таких двух сотрудников A и B, что A является начальником B.
Ваша задача — найти наименьшее возможное количество таких групп.
Выходные данные
Выведите единственное целое число — минимальное количество групп, на которые можно разделить всех сотрудников.
Примечание
В первом примере достаточно трех групп:
- Сотрудник 1
- Сотрудники 2 и 4
- Сотрудники 3 и 5
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
-1
1
2
1
-1
|
3
|