Để chuẩn bị cho lễ Giao Thừa, Bessie cùng những người bạn của cô ấy đã dựng lên một cây thông với vô vàn bóng đèn lộng lẫy. Bessie có khả năng bật tắt các bóng đèn này thông qua một chiếc điều khiển. Trước lúc bình minh, cô nàng muốn thay đổi trạng thái của một số bóng đèn theo một số thứ tự (tất nhiên một bóng đèn có thể được thay đổi trạng thái vô số lần) sao cho lúc bắt đầu và kết thúc, tất cả các bóng đèn đều tắt. Bessie nghĩ rằng cây thông trông sẽ thật ngầu nếu như tập hợp các bóng đèn được bật tạo thành một cây con có gốc là một nút nào đó trong cây thông. Cô nàng muốn thứ tự thay đổi trạng thái của các bóng đèn thoả mãn điều kiện rằng, với mọi nút trong cây, tại một thời điểm nào đó, tập hợp các bóng đèn được bật sẽ tạo thành cây con có gốc là nút này. Thêm nữa, Bessie sẽ tốn năng lượng để bật/tắt các bóng đèn nên cô nàng muốn dùng năng lượng ít nhất có thể.

Nói cách khác, cho một cây \(N\) nút có gốc là \(1\) \((2 \le N \le 2 \times 10^5)\) đại diện cho \(N\) bóng đèn. Ban đầu tất cả bóng đèn đều tắt. Ở mỗi thao tác, cô nàng có thể chuyển trạng thái của một đỉnh từ tắt sang bật và ngược lại. In ra độ dài ngắn nhất của dãy các thao tác của cô nàng sao cho:

• Mọi bóng đèn đều tắt sau dãy các thao tác.
• Tập hợp các đỉnh trong cây con có gốc là đỉnh \(r\) là các đỉnh \(v\) sao cho \(r\) nằm trên đường đi từ \(1\) đến \(v\). Với mọi cây con của cây, tập hợp các đỉnh trong cây con này bằng với tập hợp các bóng đèn được bật sau khi thực hiện xong một số thao tác.

Input

• Dòng đầu tiên là số \(N\).
• Dòng tiếp theo là các số \(p_2, p_3, ..., p_N\) \((1 \le p_i < i,\) \(p_i\) là đỉnh cha của đỉnh \(i)\).

Output

• Độ dài ngắn nhất của dãy thao tác.

Scoring

• Subtask \(1\): \(N \le 8\).
• Subtask \(2\): \(N \le 40\).
• Subtask \(3\): \(N \le 5000\).
• Subtask \(4\): Không có ràng buộc gì thêm.

3
1 1

6

Đổi trạng thái của đỉnh 2.
(Các đỉnh được bật tạo thành cây con có gốc là 2).
Đổi trạng thái của đỉnh 1.
Đổi trạng thái của đỉnh 3.
(Các đỉnh được bật tạo thành cây con có gốc là 1).
Đổi trạng thái của đỉnh 1.
Đổi trạng thái của đỉnh 2.
(Các đỉnh được bật tạo thành cây con có gốc là 3).
Đổi trạng thái của đỉnh 3.
(Tất cả các đỉnh đều tắt).