1 #include<cstdio> 2 #include<cstring> 3 #define INF 2147483000 4 using namespace std; 5 int n,m,S,T; 6 struct ss{ 7     int next,to,w,cp; 8 }x[100410]; 9 int first[4010],num;10 int dep[4010];11 int que[200000];12 char s[1010];13 void bui_(int ,int ,int );14 void build(int ,int ,int );15 int bfs();16 int dfs(int ,int );17 int main()18 {19     freopen("splay.in","r",stdin);20     freopen("splay.out","w",stdout);21     int i,j,k,ans=0,add;22     scanf("%d%d",&n,&m);23     S=0,T=3*n+1;24     scanf("%s",s+1);25     for(i=1;i<=n;i++){26         if(s[i]==‘J‘)27             bui_(S,i,1);28         if(s[i]==‘T‘)29             bui_(i,T,1);30         bui_(i,i+n,1);31         bui_(i+n,i+2*n,1);32     }33     for(i=1;i<=m;i++){34         scanf("%d%d",&j,&k);35         if(s[j]==‘J‘&&(s[k]==‘J‘||s[k]==‘E‘))36             bui_(j,k+n,1);37         if(s[j]==‘J‘&&s[k]==‘T‘)38             bui_(2*n+j,k,1);39         if(s[j]==‘E‘&&s[k]==‘T‘)40             bui_(2*n+j,k,1);41         if(s[k]==‘J‘&&(s[j]==‘J‘||s[j]==‘E‘))42             bui_(k,j+n,1);43         if(s[k]==‘J‘&&s[j]==‘T‘)44             bui_(2*n+k,j,1);45         if(s[k]==‘E‘&&s[j]==‘T‘)46             bui_(2*n+k,j,1);47     }48     while(bfs())49         while(add=dfs(S,INF))50             ans+=add;51     printf("%d",ans);52     return 0;53 }54 void bui_(int f,int t,int d){55     build(f,t,d);x[num].cp=num+1;56     build(t,f,0);x[num].cp=num-1;57 }58 void build(int f,int t,int d){59     x[++num].next=first[f];60     x[num].to=t;61     x[num].w=d;62     first[f]=num;63 }64 int bfs(){65     memset(dep,0,sizeof(dep));66     int h=0,t=1,j;67     que[t]=S;68     while(h<t){69         ++h;70         for(j=first[que[h]];j;j=x[j].next)71             if(x[j].w&&x[j].to!=S&&!dep[x[j].to]){72                 dep[x[j].to]=dep[que[h]]+1;73                 que[++t]=x[j].to;74             }75     }76     if(dep[T])return 1;77     return 0;78 }79 int dfs(int now,int min){80     int j,re=0;81     if(now==T)82         return min;83     for(j=first[now];j;j=x[j].next)84     {85         if(x[j].w&&dep[x[j].to]==dep[now]+1){86             re=dfs(x[j].to,min<x[j].w?min:x[j].w);87             if(re){88                 x[j].w-=re;89                 x[x[j].cp].w+=re;90                 return re;91             }92             dep[x[j].to]=0;93         } 94     }95     return re;96 }