Bipartite Graph from Trees

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
You are given a rooted tree T with N vertices. The vertices are numbered from 1 to N, and vertex 1 is the root. You are also given M lists A_{1}, A_{2}, .., A_{M}, where each A_{i} contains a subset of the vertices in T.
Consider a new bipartite graph G = (L, R, E), where L = {l_{1}, l_{2}, .., l_{M}} and R = {r_{1}, r_{2}, .., r_{N}} denote the two bipartitions of the vertex set and E = { (l_{i}, r_{j}), such that there exists a k which is an ancestor of j in T, and is also contained in A_{i}}. That is, there is an edge from l_{i} to r_{j} if and only if A_{i} contains a vertex of T which is an ancestor of j in T.
Note: Vertex u is an ancestor of vertex v, if it is on the path from the root to v, both end points included.
You need to compute the size of the maximum matching in G.
Input
 The first line contains a single integer, Q, which denotes the number of testcases. The description of each testcase follows.
 The first line of each testcase contains two integers: N and M, which denote the number of vertices in the tree and the number of lists respectively.
 The next line contains N  1 integers: P_{2}, P_{3}, ..., P_{N}, where P_{i} denotes the parent of vertex i in T.
 The ith of the next M lines describes the ith list A_{i}. The first integer in the line is A_{i}, which is the size of the ith list. This is followed by A_{i} integers in the same line, which denote the elements of A_{i}.
Output
 For each test case, output a single line containing the size of the maximum matching of the corresponding bipartite graph.
Constraints
 1 ≤ Q ≤ 4
 1 ≤ N ≤ 5000
 1 ≤ M ≤ 5000
 1 ≤ P_{i} ≤ N
 1 ≤ every element of a list ≤ N
 All the elements of a single list are distinct
 1 ≤ Sum of sizes of all lists in one test case ≤ 10000
Example
Input: 1 12 8 4 1 1 2 7 8 4 2 12 12 4 1 7 1 7 2 6 11 2 8 11 2 10 8 2 12 8 2 8 10 2 7 12 Output: 6
Explanation
The left bipartition of G contains 8 vertices: l_{1}, l_{2}, ..., l_{8} and the right bipartition contains 12: r_{1}, r_{2}, ..., r_{12}. Some of the edges of this bipartite graph are:
(l_{1}, r_{7}), (l_{1}, r_{6}), (l_{2}, r_{7}), (l_{2}, r_{6}), (l_{3}, r_{6}), (l_{3}, r_{11}), (l_{4}, r_{8}), (l_{4}, r_{7}), (l_{4}, r_{6}), (l_{4}, r_{11}). There are more edges.
There is a matching of size 6 in this graph which consists of the edges { (l_{1}, r_{6}), (l_{2}, r_{7}), (l_{3}, r_{11}), (l_{4}, r_{8}), (l_{5}, r_{10}), (l_{6}, r_{12})}. There is no larger matching and hence the answer is 6.
Author:  admin3 
Editorial  https://discuss.codechef.com/problems/BIPARTRE 
Tags  admin3, cook84, max, maxflow, medium, vivek1_007 
Date Added:  23072017 
Time Limit:  3.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS 
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. 