#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define maxn 410 #define maxm 40003 #define inf 1000000000 int min(int a, int b) { return a < b ? a : b; } struct E { int v, next, c; }edge[maxm]; int head[maxn], tot; int n, m; int S, T; void add(int s, int t, int c) { edge[tot].v = t; edge[tot].c = c; edge[tot].next = head[s]; head[s] = tot++; edge[tot].v = s; edge[tot].c = 0; edge[tot].next = head[t]; head[t] = tot++; } void init() { tot = 0; memset(head, -1, sizeof(head)); } int gap[maxn], dis[maxn], pre[maxn], cur[maxn]; int sap(int s, int t, int vs)// s 源点,t汇点,vs顶点总数 { int i; for(i = 0; i <= vs; i++) { dis[i] = gap[i] = 0; cur[i] = head[i]; } gap[0] = vs; int u = pre[s] = s, maxf = 0, aug = inf, v; while(dis[s] < vs) { loop: for(i = cur[u]; i != -1; i = edge[i].next) { v = edge[i].v; if(edge[i].c > 0 && dis[u] == dis[v] + 1) { aug = min(aug, edge[i].c); pre[v] = u; cur[u] = i; u = v; if(u == t) { while(u != s) { u = pre[u]; edge[cur[u]].c -= aug; edge[cur[u]^1].c += aug; } maxf += aug; aug = inf; } goto loop; } } int min_d = vs; for(i = head[u]; i != -1; i = edge[i].next) { v = edge[i].v; if(edge[i].c > 0 && dis[v] < min_d) { min_d = dis[v]; cur[u] = i; } } if( !(--gap[dis[u]])) break; ++gap[dis[u] = min_d + 1]; u = pre[u]; } return maxf; } int main() { int i, j, k, cas; scanf("%d", &cas); char buf[11]; int x; while(cas--) { scanf("%d%d", &n, &m); init(); S = n; T = m; for(i = 0; i < n; i++) { scanf("%s%d", buf, &k); if(buf[0] == 'I') add(S, i, inf); while(k--) { scanf("%d", &x); add(i, x, inf); add(x, i, 1); } } int flow = sap(S, T, n+1); if(flow >= inf) printf("PANIC ROOM BREACH\n"); else printf("%d\n", flow); } return 0; }