记录编号	83276	评测结果	AAAAAAAAAAA
题目名称	奶牛的电信	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.413 s
提交时间	2013-12-01 20:31:39	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<queue>
using namespace std;
const int SIZEN=201;
const int INF=0x3fffffff;
int n;//n个点,拆成2n个
//i是入点,n+i是出点
int S,T;
class EDGE{
public:
	int from,to,cap,flow;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
int e[SIZEN]={0},h[SIZEN]={0};
queue<int> Q;
int keyside[SIZEN]={0};
int ansflow;
void addedge(int from,int to,int cap){
	if(to==S||from==T) return;
	edges.push_back((EDGE){from,to,cap,0});
	edges.push_back((EDGE){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
void push(int x,int k){
	EDGE& now=edges[k];
	if(now.cap<=now.flow) return;
	int cf;
	if(x!=S) cf=min(now.cap-now.flow,e[x]);
	else cf=now.cap-now.flow;
	now.flow+=cf,edges[k^1].flow-=cf;
	e[now.to]+=cf,e[x]-=cf;
	if(now.to!=T&&now.to!=S&&e[now.to]) Q.push(now.to);
}
void singlenode(int x){
	int i,nowmin;
	while(e[x]){
		nowmin=INF;
		for(i=0;i<c[x].size();i++){
			EDGE& now=edges[c[x][i]];
			if(now.cap>now.flow){
				if(h[now.to]==h[x]-1){
					push(x,c[x][i]);
					if(!e[x]) return;
				}
				else nowmin=min(nowmin,h[now.to]);
			}
		}
		h[x]=nowmin+1;
	}
}
int maxflow(void){//push & relable
	int i,x;
	memset(h,0,sizeof(h));
	memset(e,0,sizeof(e));
	for(i=0;i<edges.size();i++) edges[i].flow=0;
	h[S]=n,e[S]=INF;
	for(i=0;i<c[S].size();i++) push(S,c[S][i]);
	while(!Q.empty()){
		x=Q.front();Q.pop();
		singlenode(x);
	}
	int finalflow=0;
	for(i=0;i<c[S].size();i++) finalflow+=edges[c[S][i]].flow;
	return finalflow;
}
void work(void){
	vector<int> ans;
	int i,nowflow;
	for(i=1;2*i<=n;i++){
		if(i==T||i+n/2==S) continue;
		if(edges[keyside[i]].cap>edges[keyside[i]].flow) continue;
		edges[keyside[i]].cap=0;
		nowflow=maxflow();
		if(ansflow-nowflow==1){
			ansflow=nowflow;
			ans.push_back(i);
		}
		else edges[keyside[i]].cap=1;
	}
	for(i=0;i<ans.size();i++) printf("%d ",ans[i]);
}
void init(void){
	int m,c1,c2;
	scanf("%d%d%d%d",&n,&m,&c1,&c2);
	int i,a,b;
	S=c1+n,T=c2;
	for(i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		addedge(a+n,b,INF);
		addedge(b+n,a,INF);
	}
	for(i=1;i<=n;i++){
		addedge(i,i+n,1);
		if(i==T||i+n==S) keyside[i]=-1;
		else keyside[i]=edges.size()-2;
	}
	n*=2;
}
int main(){
	freopen("telecow.in","r",stdin);
	freopen("telecow.out","w",stdout);
	init();
	ansflow=maxflow();
	printf("%d\n",ansflow);
	work();
	return 0;
}