407351: GYM102769 K Kingdom's Power

Alex is a professional computer game player.

These days, Alex is playing a war strategy game. The kingdoms in the world form a rooted tree. Alex's kingdom $$$1$$$ is the root of the tree. With his great diplomacy and leadership, his kingdom becomes the greatest empire in the world. Now, it's time to conquer the world!

Alex has almost infinite armies, and all of them are located at $$$1$$$ initially. Every week, he can command one of his armies to move one step to an adjacent kingdom. If an army reaches a kingdom, that kingdom will be captured by Alex instantly.

Alex would like to capture all the kingdoms as soon as possible. Can you help him?

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 10^5)$$$. $$$T$$$ test cases follow.

For each test case, the first line contains an integer $$$n\ (1 \le n \le 10^6)$$$, where $$$n$$$ is the number of kingdoms in the world.

The next line contains $$$(n-1)$$$ integers $$$f_2,f_3,\cdots,f_n\ (1 \le f_i < i)$$$, representing there is a road between $$$f_i$$$ and $$$i$$$.

The sum of $$$n$$$ in all test cases doesn't exceed $$$5 \times 10^6$$$.

For each test case, output one line containing "Case #x: y", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\texttt{y}$$$ is the minimum time to conquer the world.

2
3
1 1
6
1 2 3 4 4

Case #1: 2
Case #2: 6