根据小朋友的意愿和他们之间的关系建一个图
如果 A 想睡觉就从 S 连一条边到 A ，反之从 A 连一条边到 T
如果 A，B 是好朋友，则他们之间连双向边（友谊是相互的）
那么对于任意一条从 S 到 T 的只经过两个小朋友的路径，则表示一种冲突
（因为与 S 相连说明 A 要睡觉，但是有朋友不想睡觉，那么就产生了冲突）
考虑让 A 转变意愿，产生的 1 的花费
相当于把 S 到 A 的边给割掉了
让另一个小朋友转变意愿去睡觉也同样把从ta到 T 的边给掉，产生 1 的花费
如果最后没有从 S 到 T 的路径了，那么就不存在任何冲突了，反之则一定存在（显然）
所以从 S 出发的边边权为 1，朋友之间边权为 INF，从小朋友到 T 边权为 1
然后最小割
// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,INF=1e9+7; int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt=1,Fir[N]; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; } int n,m,S,T,ans; int dep[N]; queue <int> q; int BFS() { for(int i=1;i<=T;i++) dep[i]=0; q.push(S); dep[S]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]||!val[i]) continue; q.push(v); dep[v]=dep[x]+1; } } for(int i=1;i<=T;i++) Fir[i]=fir[i]; return dep[T]; } int dfs(int x,int mif) { if(x==T||!mif) return mif; int fl=0,res=0; for(int i=Fir[x];i;i=from[i]) { Fir[x]=i; int &v=to[i]; if(dep[v]!=dep[x]+1) continue; if( res=dfs(v,min(mif,val[i])) ) { fl+=res; mif-=res; val[i]-=res; val[i^1]+=res; if(!mif) break; } } return fl; } int main() { int a,b; n=read(),m=read(); S=n+m+1; T=n+m+2; for(int i=1;i<=n;i++) { a=read(); a ? add(S,i,1) : add(i,T,1); } for(int i=1;i<=m;i++) { a=read(); b=read(); add(a,b,1); add(b,a,1); } while(BFS()) ans+=dfs(S,INF); printf("%d",ans); return 0; }