Hawala Arrests

All submissions for this problem are available.
At Intensely Corrupt Private Company (ICPC), everyone is, well, intensely corrupt. There are a total of N employees, numbered from 1 to N. The company is structured hierarchically, like a tree. ie. there is a CEO, who happens to be numbered 1. Every other employee has exactly 1 manager directly above him, and following the chain of managers up from any employee will take you to the CEO, who has no manager above him. To avoid paying taxes, the employees use Hawala traders to transfer money to secret foreign accounts. There are a total of K Hawala traders. Each employee uses some of these K different Hawala traders (possibly none, or possibly all of the K). The Hawala traders are very careful. They start out with one client in the company. And then, they take up a new client from the company only if the new client happens to be the manager of one of their existing clients, or the new client's manager is one of their existing clients. So this means that for each of the K Hawala traders, their clientlist in the company is very closeknit.
You are working for the investigation team investigating the Hawala traders. Luckily, you have discovered an unhappy employee of this company, who wants to bring down this entire operation. This employee has given you, for each Hawala trader, the employees of the company who use that Hawala trader. Your agency wants to bring all the K Hawala traders down. To bring down a Hawala trader, at least 1 of the employees who is a client of that trader has to be arrested. Find the minimum number of arrests that you must make to bring down all the K Hawala traders.
Input
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N, K, denoting the number of employees, and the number of Hawala traders, respectively.
The next line contains N1 integers ,separated by single spaces: M_{2}, M_{3}, .., M_{N}, denoting that Employee i's manager is M_{i}. Note that Employee 1 is the CEO, and hence M_{1} does not exist.
K lines follow, where the i^{th} line describes the client list of the i^{th} Hawala trader. Each of these lines starts out with an integer S_{i}, which is the size of the client list, and then S_{i} space separated integers follow, in the same line: C_{i1}, C_{i2}, .., C_{iSi}, denoting that employee C_{ij} is a client of the i^{th} Hawala trader.
Output
For each test case, output a single line containing the answer, which is the minimum number arrests that should be made.
Constraints
 1 ≤ T ≤ 3
 1 ≤ N, K ≤ 10^{6}
 1 ≤ M_{i} ≤ N
 1 ≤ S_{i} ≤ 10^{6}
 1 ≤ C_{ij} ≤ N
 The summation of sizes of all the K client lists will be less than or equal to 10^{6}.
 Each of the K client lists will satisfy the criteria that they are 'closeknit', as explained above.
Example
Input: 1 5 3 3 1 1 3 3 2 5 3 2 1 3 2 4 1 Output: 2
Explanation
The client lists are {2,3,5}, {1,3} and {1,4}. Arresting Employees 1 and 3 will bring down all the 3 Hawala traders. You can verify that it cannot be done with only 1 arrest. Hence the answer is 2.Author:  admin3 
Editorial  https://discuss.codechef.com/problems/AMR16G 
Tags  admin3 
Date Added:  20122016 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 