Để chào đón Tết Nguyên Đán, thầy Trí cùng các em học trò trang trí một cây mai khổng lồ. Trên mỗi đỉnh của cây, các em treo một bao lì xì đặc biệt có hai mặt: mặt xanh và mặt đỏ. Ban đầu, tất cả bao lì xì đều quay mặt xanh. Trong một thao tác, thầy Trí có thể yêu cầu một em học trò lật bao lì xì ở đúng một đỉnh (xanh → đỏ hoặc đỏ → xanh). Thầy Trí muốn sắp xếp một dãy thao tác lật (có thể lật một đỉnh nhiều hơn một lần) sao cho:

1. Với mọi cây con trong \(N\) cây con của cây, sẽ có một thời điểm mà tập các đỉnh đang quay mặt đỏ chính xác là tập đỉnh của cây con đó.
2. Kết thúc toàn bộ dãy thao tác, tất cả bao lì xì lại quay về mặt xanh (không còn đỉnh nào đỏ). Vì mỗi lần lật bao lì xì đều tốn công sức, thầy Trí muốn tổng số lần lật là nhỏ nhất có thể. Hãy giúp thầy tìm số lần lật tối thiểu.

Phát biểu hình thức

Cho một cây gốc có \(N\) đỉnh (\(2 \le N \le 2 \cdot 10^5\)), đánh số từ \(1\) đến \(N\), gốc tại đỉnh \(1\). Mỗi đỉnh ban đầu đều ở trạng thái xanh. Mỗi thao tác lật một đỉnh duy nhất (xanh ↔ đỏ). Định nghĩa cây con gốc \(r\) gồm tất cả đỉnh \(v\) sao cho \(r\) nằm trên đường đi từ gốc \(1\) đến \(v\) (kể cả \(r\)). Hãy tìm độ dài nhỏ nhất của một dãy thao tác thỏa mãn đồng thời:

• Với mỗi cây con trong \(N\) cây con, tồn tại một thời điểm mà tập đỉnh đỏ đúng bằng tập đỉnh của cây con đó.
• Sau khi thực hiện xong toàn bộ dãy, mọi đỉnh đều quay về mặt xanh.

Dữ liệu vào:

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(p_2, p_3, \dots, p_N\) \((1 \le p_i < i)\), trong đó \(p_i\) là cha của đỉnh \(i\).

Ràng buộc dữ liệu vào:

• 25% số điểm tương ứng với các test có \(N \le 8\).
• 25% số điểm tương ứng với các test có \(N \le 40\).
• 25% số điểm tương ứng với các test có \(N \le 5000\).
• 25% số điểm còn lại không ràng buộc gì thêm \((N \le 2 \cdot 10^5)\).

Kết quả:

• Một số nguyên duy nhất - số lần lật tối thiểu.

Input 1

3
1 1

Output 1

6

Giải thích:

• Cây có \(3\) cây con: \(\{1,2,3\}\), \(\{2\}\), \(\{3\}\). Một dãy thao tác tối ưu:
  • Lật đỉnh \(2\) (→ đỏ). Tập đỉnh đỏ: \(\{2\}\) ✅ Cây con gốc \(2\).
  • Lật đỉnh \(1\) (→ đỏ). Tập đỉnh đỏ: \(\{1, 2\}\).
  • Lật đỉnh \(3\) (→ đỏ). Tập đỉnh đỏ: \(\{1, 2, 3\}\) ✅ Cây con gốc \(1\).
  • Lật đỉnh \(1\) (→ xanh). Tập đỉnh đỏ: \(\{2, 3\}\).
  • Lật đỉnh \(2\) (→ xanh). Tập đỉnh đỏ: \(\{3\}\) ✅ Cây con gốc \(3\).
  • Lật đỉnh \(3\) (→ xanh). Tập đỉnh đỏ: \(\{\}\) ✅ Kết thúc, tất cả xanh.
• Tổng cộng 6 lần lật.