记录编号	495589	评测结果	AAAAAAAAAA
题目名称	[HAOI 2017]新型城市化	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.246 s
提交时间	2018-04-21 10:34:46	内存使用	2.49 MiB

#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define inf (int)1e9
using namespace std;
const int maxn=10010;
const int maxm=150010;
struct Edge{int from,to,cap,flow;};
stack<int>st;
vector<Edge>edges;
vector<int>G[maxn];
vector<int>p[maxn];
vector<pair<int,int> >ans;
int n,m,s,t,idx,cnt,a[maxm],b[maxm],d[maxn],belong[maxn];
int ed[maxm],dfn[maxn],low[maxn],cur[maxn],color[maxn];
bool vis[maxn];
void addedge(int from,int to,int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int h=edges.size();
	G[from].push_back(h-2),G[to].push_back(h-1);
}
bool bfs(){
	memset(vis,0,sizeof(vis));
	queue<int>q;
	vis[s]=1,d[s]=0,q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<(int)G[u].size();i++){
			Edge e=edges[G[u][i]];
			if(!vis[e.to]&&e.cap>e.flow)d[e.to]=d[u]+1,vis[e.to]=1,q.push(e.to);
		}
	}
	return vis[t];
}
int dfs(int x,int v){
	if(x==t||!v)return v;
	int f,flow=0;
	for(int&i=cur[x];i<(int)G[x].size();i++){
		Edge&e=edges[G[x][i]];
		if(d[e.to]==d[x]+1&&(f=dfs(e.to,min(v,e.cap-e.flow)))){
			flow+=f,e.flow+=f,v-=f;
			edges[G[x][i]^1].flow-=f;
			if(!v)break;
		}
	}
	return flow;
}
int dinic(){
	int flow=0;
	while(bfs())memset(cur,0,sizeof(cur)),flow+=dfs(s,inf);
	return flow;
}
void bfs(int x){
	queue<int>q;
	color[x]=0,q.push(x);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<(int)p[u].size();i++){
			int v=p[u][i];
			if(color[v]==-1)color[v]=color[u]^1,q.push(v);
		}
	}
}
void tarjan(int x){
	st.push(x);
	low[x]=dfn[x]=++idx;
	for(int i=0;i<(int)G[x].size();i++){
		Edge e=edges[G[x][i]];
		if(e.cap==e.flow)continue;
		int u=e.to;
		if(!dfn[u])tarjan(u),low[x]=min(low[x],low[u]);
		else if(!belong[u])low[x]=min(low[x],dfn[u]);
	}
	if(low[x]==dfn[x]){
		cnt++;int k=-1;
		while(k!=x&&!st.empty()){
			k=st.top();st.pop();
			belong[k]=cnt;
		}
	}
}
int main(){
	freopen("newcity.in","r",stdin);
	freopen("newcity.out","w",stdout);
	scanf("%d%d",&n,&m);
	s=0,t=n+1;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i],&b[i]);
		p[a[i]].push_back(b[i]),p[b[i]].push_back(a[i]);
	}
	memset(color,-1,sizeof(color));
	for(int i=1;i<=n;i++)if(color[i]==-1)bfs(i);
	for(int i=1;i<=n;i++){
		if(color[i])addedge(s,i,1);
		else addedge(i,t,1);
	}
	for(int i=1;i<=m;i++){
		if(color[a[i]])addedge(a[i],b[i],1),ed[i]=G[a[i]][G[a[i]].size()-1];
		else addedge(b[i],a[i],1),ed[i]=G[b[i]][G[b[i]].size()-1];
	}
	dinic();cnt=idx=0;
	for(int i=0;i<=n+1;i++){
		if(!dfn[i])
			tarjan(i);
	}
	for(int i=1;i<=m;i++){
		Edge e=edges[ed[i]];
		if(e.cap!=e.flow)continue;
		int u=e.from,v=e.to;
		if(u>v)swap(u,v);
		if(belong[u]==belong[v])continue;
		ans.push_back(make_pair(u,v));
	}
	sort(ans.begin(),ans.end());
	printf("%d\n",ans.size());
	for(int i=0;i<(int)ans.size();i++)
		printf("%d %d\n",ans[i].first,ans[i].second);
	return 0;
}