记录编号	399255	评测结果	AAAAAAAAAA
题目名称	2669.[HAOI 2017]新型城市化	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.241 s
提交时间	2017-04-25 20:52:31	内存使用	66.11 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
struct edge{int f,t,g;}w[N];
int n,m,head[N],tail[N],next[N],cnt;
void add(int f,int t,int g){
	w[++cnt]=(edge){f,t,g};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	w[++cnt]=(edge){t,f,0};
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
int op(int x){return x&1?x+1:x-1;}
struct st{
	int x,i,df;
	st(int X=0,int DF=0){x=X;i=head[x];df=DF;}
}z[N];
int top,l[N],s,t;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[op(z[i].i)].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=s;i<=t;i++) l[i]=0;
	l[s]=1;Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		if (l[t]) continue;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[t]) return 0;
	z[top=1]=st(s,1e9);
	while (top){
		if (V==t){change();top--;E=next[E];}else
		if (!E){l[V]=0;top--;E=next[E];}else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=st(w[E].t,min(F,w[E].g)),top++;
		else E=next[E];
	}
	return 1;
}
int dfn[N],low[N],stack[N],fa[N],h;
bool ins[N];
void tarjan(int x){
	static int cnt=0;
	dfn[x]=low[x]=++cnt;
	stack[++h]=x;
	ins[x]=1;
	for (int i=head[x];i;i=next[i])
	if (w[i].g){
		int v=w[i].t;
		if (!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);else
		if (ins[v]) low[x]=min(low[x],dfn[v]);
	}
	if (low[x]==dfn[x]){
		for (;stack[h]!=x;h--)
			ins[stack[h]]=0,fa[stack[h]]=x;
		fa[x]=x;ins[x]=0;h--;
	}
}
int tp[N];
void paint(int x,int C){
	tp[x]=C;
	for (int i=head[x];i;i=next[i])
	if (!tp[w[i].t]) paint(w[i].t,-C);
}
pair<int,int> p[N];
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++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v,0);
	}
	for (int i=1;i<=n;i++)
	if (!tp[i]) paint(i,1);
	for (int i=1;i<=cnt;i++)
	if (tp[w[i].f]==1) w[i].g=1;
	for (int i=1;i<=n;i++)
	if (tp[i]==-1) add(i,t,1);else add(s,i,1);
	while (dinic());
	for (int i=s;i<=t;i++)
		if (!dfn[i]) tarjan(i);
	int ans=0;
	for (int i=1;i<=m*2;i++)
	if (tp[w[i].f]==1&&!w[i].g&&fa[w[i].f]!=fa[w[i].t]){
		if (w[i].f>w[i].t) swap(w[i].f,w[i].t);
		p[++ans]=make_pair(w[i].f,w[i].t);
	}
	printf("%d\n",ans);
	sort(p+1,p+ans+1);
	for (int i=1;i<=ans;i++) printf("%d %d\n",p[i].first,p[i].second);
	return 0;
}