//Malvika Raj Joshi #include #include #include #include #include #include #define NMAX 10010 #define MMAX 20010 #define VMAX 30010 using namespace std; vector lst[MMAX]; vector child[NMAX]; int par[NMAX]; int sz[NMAX]; vector > adj[VMAX]; vector rev[VMAX]; int N,M,V; void clear(){ int i; for(i = 0; i < V; ++i) adj[i].clear(), rev[i].clear(); for(i = 0; i < M; ++i) lst[i].clear(); for(i = 0; i < N; ++i) child[i].clear(); } int dfs(int v){ int i; sz[v]=1; for(i = 0; i < (int)child[v].size(); ++i){ sz[v] += dfs(child[v][i]); } return sz[v]; } inline void add_edge(int i, int k, int cap){ rev[i].push_back(adj[k].size()); rev[k].push_back(adj[i].size()); adj[i].push_back(make_pair(k,cap)); adj[k].push_back(make_pair(i,0)); } int init(){ int i,j,k; dfs(0); V = N+M; for(i = 0; i < M; ++i){ for(j = 0; j < (int)lst[i].size(); ++j){ k = lst[i][j]; add_edge(N+i,k,1); } add_edge(V,N+i,1); } for(i =1; i < N; ++i){ add_edge(i,par[i],sz[i]); } return V++; } int Q[VMAX]; int H,T; int vis[NMAX]; int prv[NMAX]; int cap[NMAX]; int aug_path(int src, int tar){ int v,i,u; H = T = 0; memset(vis,0,sizeof(vis)); prv[src] = -1, cap[src] = (1e9), vis[src] = 1; Q[T++] = src; while(H < T){ v = Q[H++]; for(i = 0; i < (int)adj[v].size(); ++i){ u = adj[v][i].first; if(vis[u] || !adj[v][i].second) continue; prv[u] = rev[v][i], cap[u] = adj[v][i].second, vis[u] = 1; assert(adj[u][prv[u]].first == v); Q[T++] = u; } } return vis[tar]; } int max_flow(int src, int tar){ int tot,flow, v, i,p; tot = 0; while(aug_path(src,tar)){ flow = cap[src]; v = tar; while(prv[v] >= 0){ flow = min(flow,cap[v]); v = adj[v][prv[v]].first; } tot += flow; v= tar; while(prv[v] >= 0){ i = prv[v]; p = adj[v][i].first; adj[v][i].second += flow; assert(adj[v][i].first == p); i = rev[v][i]; adj[p][i].second -= flow; assert(adj[p][i].first == v); v = p; } } return tot; } int main(){ int i,k,t,n; scanf("%d",&t); while(t--){ scanf("%d%d",&N,&M); par[0]=-1; for(i = 1; i < N; ++i){ scanf("%d",&par[i]); --par[i]; child[par[i]].push_back(i); } for(i = 0; i < M; ++i){ scanf("%d",&n); while(n--){ scanf("%d",&k); lst[i].push_back(--k); } } init(); printf("%d\n",max_flow(V-1,0)); clear(); } return 0; }