很久很久之前，树林里住着一群兔子。但是不幸的时，森林里还有一匹狼，这匹狼隔三差五就来骚扰兔子，兔子为了抵抗狼的袭击，也组织了军队来与狼战斗。这一系列战役发生在很久之前了，现在的人们只能通过史书来了解当时的战役。
我们假设一共有N只兔子，编号为1-N，史书上记载了K场兔子与狼之间的战役。每场战役，兔子们派出这N只兔子的中的若干只（即一个集合）去与狼战斗，史书上同时也记录了这场战役的结果（兔子胜利或者狼胜利）。但是史书的记录并不可靠，有时会出现矛盾的情况，矛盾的情况有以下两种：

1、有一场战役兔子集合S去迎战狼，并且兔子胜利，但是还有一场战役，兔子集合S’去迎战狼，但是兔子失败了。其中S是S’的子集。（这种情况对应了，已经取得胜利的兔子们再加上了一些兔子却失败了）

2、有一场战役兔子集合S去迎战狼，并且兔子失败，但是还有一场战役，兔子集合S’去迎战狼，但是兔子胜利了。其中S是S’的超集。（这种情况对应了，已经失败的兔子们再减去了一些兔子却胜利了）

你需要修改史书上若干条记录的结果（即兔子胜利改成失败，或者失败改成胜利），使得以上两种矛盾都不会出现。

输入格式：

第一行两个整数N和K，分别表示兔子的个数和史书上记录的个数
接下来K行，每行表示一条记录。每个记录由一个整数h开始，表示这场战役由h个兔子参战，在接下来h个整数，表示参与这场战役的兔子们，保证这h个编号互不相同。再最后一个字母W或者F，W表示这场战役兔子胜利，F表示兔子失败

输出格式：

一行一个整数，表示最小修改的记录条数

数据范围

$N,K\le 1000$

解法

首先根据集合的包含关系连边，注意如果两个集合相同，也要连边。然后我们发现唯一一种冲突情况就是一个大集合输了，一个小集合反而赢了。如果我们将原图中一个胜了的集合的权值设为1，一个输了的集合权值设为0，并且将权值为1的集合与S连边，权值为0的集合向T连边，每条边容量为1，再链接那些有冲突的边，容量设为inf,那么答案就是这张图的最小割。
考虑正确性：一条没有冲突的边对答案实际上没有影响，因为如果这条边的大集合和某一个集合有冲突，那么小集合也一定和那个集合有冲突。如果是小集合有冲突，那对于大集合而言没有影响。

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
inline int read(){char c=getchar();int t=0,f=1;while((!isdigit(c))&&(c!=EOF)){if(c=='-')f=-1;c=getchar();}while((isdigit(c))&&(c!=EOF)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}return t*f;
}
int n,k;
struct node{int a[1005],h,st;
}a[1005];
struct edge{int v,p,w;
}e[2000005];
int h[1005],cnt=1;
vector<int> g[1005];
inline void add(int a,int b,int c){e[++cnt].p=h[a];e[cnt].v=b;e[cnt].w=c;h[a]=cnt;
}
int s,t,dis[1005],ht[1005];
bool bfs(){queue<int> q;while(!q.empty())q.pop();q.push(s);memset(dis,-1,sizeof(dis));dis[s]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=h[u];i;i=e[i].p){int v=e[i].v;if(e[i].w&&(dis[v]==-1)){dis[v]=dis[u]+1;//  printf("%d %d\n",v,dis[v]);q.push(v);if(v==t)return 1;}}}return 0;
}
int dfs(int u,int rest){if(u==t||rest==0)return rest;int tot=0;for(int &i=ht[u];i;i=e[i].p){int v=e[i].v;if(e[i].w&&(dis[v]==dis[u]+1)){int di=dfs(v,min(rest,e[i].w));e[i].w-=di;e[i^1].w+=di;rest-=di;tot+=di;if(rest==0)break;}}return tot;
}
int dinic(){int ans=0;while(bfs()){for(int i=s;i<=t;i++)ht[i]=h[i];ans+=dfs(s,inf);}return ans;
}
signed main(){
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);n=read(),k=read();s=0,t=k+1;for(int i=1;i<=k;i++){int h=read();for(int j=1;j<=h;j++){int x=read();a[i].a[x]++;}a[i].h=h;char c;cin>>c;if(c=='W'){add(s,i,1);add(i,s,0);a[i].st=1;}else {add(i,t,1);add(t,i,0);a[i].st=0;}}for(int i=1;i<=k;i++){for(int j=1;j<=k;j++){if(a[i].h<a[j].h)continue;int flag=1;for(int x=1;x<=n;x++){if(a[j].a[x]&&(!a[i].a[x])){flag=0;break;}}if(flag){if(a[j].st==1&&a[i].st==0){//printf("%d %d\n",i,j);add(j,i,inf);add(i,j,0);}}}}printf("%d\n",dinic());return 0;
}