Description

Input

Output

Sample Input

Sample Output

HINT

【题解】裸题，最小割。

# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <queue>
using namespace std;

const int M=300010,Ms=310;
int n,m,head[M],next[M],flow[M],to[M],c[M],tot=1,S,T;
inline void add(int u,int v,int fl) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	flow[tot]=fl;
}

inline void Add(int u,int v,int fl) {
	add(u,v,fl);
	add(v,u,0);
}

queue<int> q;

inline void qc() {
	while(!q.empty()) q.pop();
}

inline bool bfs() {
	qc(); memset(c,-1,sizeof(c));
	q.push(S);c[S]=1;
	while(!q.empty()) {
		int top=q.front(); q.pop();
		for (int i=head[top];i;i=next[i]) {
			int _to=to[i];
			if(c[_to]>=0 || flow[i]==0) continue;
			c[_to]=c[top]+1;
			q.push(_to);
			if(_to==T) return 1;
		}
	}
	return 0;
}

inline int dfs(int x,int low) {
	if(x==T) return low;
	int fl,r=low;
	for (int i=head[x];i;i=next[i]) {
		int _to=to[i];
		if(c[_to]!=c[x]+1 || flow[i]==0) continue;
		fl=dfs(_to,min(r,flow[i]));
		r-=fl;
		flow[i]-=fl;
		flow[i^1]+=fl;
		if(!r) return low;
	}
	if(r==low) c[x]=-1;
	return low-r;
}

int main() {
	scanf("%d%d",&n,&m);
	S=0,T=n+1;
	for (int i=1,cant;i<=n;++i) {
		scanf("%d",&cant);
		if(cant==1) Add(S,i,1);
		else Add(i,T,1);
	}
	for (int i=1,u,v;i<=m;++i) {
		scanf("%d%d",&u,&v);
		Add(u,v,1);
		Add(v,u,1);
	}
	
	int ans=0;
	
	while(bfs()) ans+=dfs(S,200011300);
	printf("%d\n",ans);
	
	return 0;
}