记录编号	401174	评测结果	AAAAAAAAAA
题目名称	[HAOI 2017]新型城市化	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	0.337 s
提交时间	2017-05-01 15:59:14	内存使用	33.50 MiB

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define up(i,j,n)       for(int i=j;i<=n;i++)
#define doww(i,j,n)     for(int i=j;i>=n;i--)
#define cmax(a,b)       a=max(a,b)
#define cmin(a,b)       a=min(a,b)
#define pii             pair<int,int>
#define fi              first
#define se              second
#define Auto(i,node)    for(int i=LINK[node];i;i=e[i].next)
#define FILE            "newcity"

const int MAXN=3e5+5;
const int oo=0x3f3f3f3f;

int N,M,S,T,col[MAXN],sta[MAXN],top=0,dfn[MAXN],low[MAXN],dfsclock=0,BCC[MAXN],bccs;
int nxt[MAXN];
pii ed[MAXN];
bool iskey[MAXN],ismat[MAXN],vis[MAXN],used[MAXN];

struct Graph{
        struct edge{
                int y,next;
        }e[MAXN<<1];
        int LINK[MAXN],len;
        inline void insert(int x,int y){
                e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;
        }
        inline void Insert(int x,int y){
        	insert(x,y);
        	insert(y,x);
        }
        void Colit(int node){
        	Auto(i,node)if(!col[e[i].y]){
        		col[e[i].y]=(col[node]==1?-1:1);
        		Colit(e[i].y);
        	}
        }
        void Clear(){
        	memset(LINK,0,sizeof(LINK));
        	len=0;
        }
        void DFS(int node){
        	vis[node]=1;
        	Auto(i,node)if(!vis[e[i].y])
        		DFS(e[i].y);
        }
        void Tarjan(int node){
        	dfn[node]=low[node]=++dfsclock;
        	sta[++top]=node;vis[node]=1;
        	Auto(i,node)if(!dfn[e[i].y]){
        		Tarjan(e[i].y);
        		cmin(low[node],low[e[i].y]);
        	}else if(vis[e[i].y])cmin(low[node],dfn[e[i].y]);
        	if(low[node]==dfn[node]){
        		bccs++;int tmp;
        		do{
        			tmp=sta[top--];
        			BCC[tmp]=bccs;
        			vis[tmp]=0;
        		}while(tmp!=node);
        	}
        }
}G1,G2;


namespace Maxflow{
        struct edge{
                int y,next,flow,rev;
        }e[MAXN<<1];
        int LINK[MAXN],len,level[MAXN];
        deque<int>q;
        inline void insert(int x,int y,int flow,int rev){
                e[++len].next=LINK[x];LINK[x]=len;
                e[len].y=y;e[len].flow=flow;e[len].rev=len+rev;
        }
        inline void Insert(int x,int y,int flow){
                insert(x,y,flow,1);
                insert(y,x,0,-1);
        }
        bool makelevel(){
        	memset(level,-1,sizeof(level));
        	q.push_back(S);level[S]=0;
        	while(!q.empty()){
        		int node=q.front();q.pop_front();
        		Auto(i,node)if(level[e[i].y]==-1&&e[i].flow){
        			level[e[i].y]=level[node]+1;
        			q.push_back(e[i].y);
        		}
        	}
        	return level[T]!=-1;
        }
        int addflow(int node,int flow){
        	if(node==T||!flow)return flow;
        	int maxflow=0,d;
        	Auto(i,node)if(e[i].flow&&level[e[i].y]==level[node]+1)
        		if(d=addflow(e[i].y,min(e[i].flow,flow-maxflow))){
        			maxflow+=d;
        			e[i].flow-=d;
        			e[e[i].rev].flow+=d;
        		}
        	if(!maxflow)level[node]=-1;
        	return maxflow;
        }
        void Dinic(){
        	int ans=0,d;
        	while(makelevel())
        		while(d=addflow(S,oo))
        			ans+=d;
        }
        void Build(){
           	Auto(i,S)if(e[i].flow==0)ismat[e[i].y]=1;
        	Auto(i,T)if(e[e[i].rev].flow==0)ismat[e[i].y]=1;
        	up(node,1,N)if(col[node]==-1)Auto(i,node)if(e[i].y!=S){
        		if(e[i].flow==0){
        			G2.insert(e[i].y,node);
        			nxt[node]=e[i].y;
        		}
        		else		G2.insert(node,e[i].y);
        	}
        	vis[S]=vis[T]=1;
        	up(i,1,N)if(col[i]==-1&&!ismat[i]&&!vis[i])
        		G2.DFS(i);
        	memcpy(used,vis,sizeof(used));
        	memset(vis,0,sizeof(vis));
        	G2.Clear();
        	up(node,1,N)if(col[node]==1)Auto(i,node)if(e[i].y!=T){
           		if(e[e[i].rev].flow==0){
           			G2.insert(e[i].y,node);
           			nxt[node]=e[i].y;
           		}
        		else			G2.insert(node,e[i].y);     	
        	}
        	vis[S]=vis[T]=1;
        	up(i,1,N)if(col[i]==1&&!ismat[i]&&!vis[i])
        		G2.DFS(i);
   		up(i,1,N)used[i]|=vis[i];
        	up(i,1,N)if(!used[i]&&ismat[i])iskey[i]=1;     	
        }
}

namespace solution{
        void Prepare(){
                scanf("%d%d",&N,&M);
                up(i,1,M){
                        int x,y;
                        scanf("%d%d",&x,&y);
                        if(x>y)swap(x,y);
                        ed[i]=make_pair(x,y);
                        G1.Insert(x,y);
                }
                sort(ed+1,ed+M+1);
                S=N+1;T=N+2;
                up(i,1,N)if(!col[i])G1.Colit(i);
                up(i,1,M){
                	int x=ed[i].fi,y=ed[i].se;
                	if(col[x]==1)swap(x,y);
                	Maxflow::Insert(x,y,1);
                }
                up(i,1,N){
                	if(col[i]==-1)		Maxflow::Insert(S,i,1);
                	else if(col[i]==1)	Maxflow::Insert(i,T,1);
                }
                Maxflow::Dinic();//转化为二分图然后跑最大匹配
                Maxflow::Build();//重新建图
        }
        void Solve(){
        	// 求出所有关键点
        	up(i,1,N)if(!dfn[i])G2.Tarjan(i);
        	int ans=0;
        	up(i,1,M){
        		int x=ed[i].fi,y=ed[i].se;
        		if(nxt[x]!=y||BCC[x]==BCC[y])continue;
        		if(iskey[x]||iskey[y])ans++;
        	}
        	cout<<ans<<endl;
        	up(i,1,M){
        		int x=ed[i].fi,y=ed[i].se;
        		if(nxt[x]!=y||BCC[x]==BCC[y])continue;
        		else if(iskey[x]||iskey[y])
        			printf("%d %d\n",x,y);
        	}
        }
}

int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}