Server Time: Wed Jun 19, 2019 4:50 pm
Welcome ( logout
1290 - The Great Merger
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Woohoo and MarcoHard are two prominent software companies. But due to the rise of rival firms, they decided that they need to merge in order to compete with them. For this, the management in Woohoo and MarcoHard are facing some troubles.

Both Woohoo and MarcoHard maintain a hierarchy of employees. In both companies, the head of the company is the CEO. Every other employee has exactly one immediate superior.

To make the merger successful, they have to maintain exactly same hierarchy in both the companies. They decided not to fire any of the employees. They can change the name of the employee's post (e.g. one company has a post for 'Software Developer', in other company it is called 'Code Ninja'), but they can't promote or demote anyone (e.g. they can't make Developer a Project Manager or vice versa), nor can they break the existing hierarchy (that is if a is an immediate superior of b, they should be the same in the new hierarchy). But they can make new posts and hire new employees. Now, they need to make a similar hierarchy by hiring minimum number of employees. Since, they are people in HR, and not much familiar with computing algorithms, they are finding it really tough to figure out how many people to hire. So, you are asked to this job for them. And guess what, you may be awarded a balloon if you can help them in this great dilemma.


Input starts with an integer T (≤ 200), denoting the number of test cases.

Each test case contains a blank line and two more lines, the hierarchy of WooHoo and Marcohard. Each hierarchy description starts with an integer N (1 ≤ N ≤ 100), the number of employees except the CEO, followed by N integers, each describing the immediate superior of that employee. The CEO is identified by 0th employee and every other employee is identified by an integer between 1 and N.

You can assume that, the hierarchy is valid, that is every employee is direct or indirect subordinate of the CEO and no one is a direct or indirect superior of himself.


For each test case, print the case number and the minimum number employees to hire. Both WooHoo and MarcoHard can hire, so, this number will be the total number of new employees hired by these two companies.

Sample Input

Output for Sample Input



4 0 0 1 1

4 0 1 2 2


4 0 0 1 1

4 0 0 2 2

Case 1: 4

Case 2: 0


Problem Setter: Manzurur Rahman Khan
Special Thanks: Jane Alam Jan (Solution, Dataset)
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan