Phân lớp ca sinh hoạt

Bối cảnh và bài toán

Một công ty cần chia toàn bộ nhân sự thành các nhóm sinh hoạt sao cho trong cùng một nhóm không có ai là cấp trên trực tiếp hoặc gián tiếp của người khác. Quan hệ quản lý tạo thành một rừng có hướng từ quản lý xuống cấp dưới và không có chu trình.

Yêu cầu

Tìm số nhóm ít nhất cần thiết để thỏa điều kiện.

Input

• Dòng 1 chứa n.
• n dòng tiếp theo; dòng i chứa manager[i]. Giá trị -1 nghĩa là nhân sự i không có quản lý trực tiếp.

Output

In một số nguyên: số nhóm ít nhất.

Ràng buộc

• 1 <= n <= 2000
• manager[i] = -1 hoặc 1 <= manager[i] <= n
• Quan hệ quản lý không có chu trình.

Chấm điểm

Ví dụ 1

Input

5
-1
1
2
1
-1

Output

3

Giải thích. Chuỗi quản lý 1→2→3 có độ sâu 3 nên cần ít nhất ba nhóm.

Ví dụ 2

Input

3
-1
-1
-1

Output

1

Giải thích. Không ai là cấp trên của ai; mọi người có thể ở cùng một nhóm.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 115A – Party.