记录编号	365497	评测结果	RRRRRRRRRRRRRRRRRRRRRRRRR
题目名称	[Keller战纪·正传·妖姬篇][HZOI 2015]Keller非.a.t.e	最终得分	0
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	未通过
代码语言	C++	运行时间	0.021 s
提交时间	2017-01-20 17:24:23	内存使用	1.86 MiB

#include <queue>
#include <cstdio>
#include <cstring>
const int MAXN=260;
const int MAXM=MAXN*MAXN*3;
struct FFT {
	int f[MAXN];
	void __init__(int N) 
		{for(int i=0;i<=N;++i)f[i]=i;}
	int& find(int i) {while(i!=f[i])i=f[i]=f[f[i]];return f[i];}
	void join(int a,int b){a=find(a);b=find(b);if(a!=b)f[a]=b;}
	int &operator[](const int&i){return find(f[i]);}
}fc;
struct PATH {
	int to,next;
	PATH() {to=next=-1;}
	PATH(int a,int b):to(a),next(b){}
};
struct PIC {
	int lens;
	bool vis[MAXN];
	int mark[MAXN];
	int head[MAXN];
	int match[MAXN];
	int next[MAXN];
	PATH table[MAXM];
	std::deque<int>q;
	PIC() {memset(head,-1,sizeof(head));lens=0;}
	void add(int from,int to) {
		table[++lens]=PATH(to,head[from]);head[from]=lens;
		//table[++lens]=PATH(from,head[to]);head[to]=lens;
	}
	int lca(int x,int y) {
		static int lock=0;++lock;
		while(true) {
			if(x!=-1) {
				x=fc[x];
				if(vis[x]==lock)return x;
				vis[x]=lock;
				if(match[x]!=-1)x=next[match[x]];
				else x=-1;
			}std::swap(x,y);
		}return 0;
	}
	void group(int x,int y) {
		while(x!=y) {
			int b=match[x],c=next[b];
			if(fc[c]!=y)next[c]=b;
			if(mark[b]==2){mark[b]=1;q.push_back(b);}
			if(mark[c]==2){mark[c]=1;q.push_back(c);}
			fc.join(x,b);fc.join(b,c);
			x=c;
		}
	}
	void flower(int from,int N) {
		//printf("From:%d\n",from);
		memset(vis,0,sizeof(vis));
		memset(mark,0,sizeof(mark));
		memset(next,-1,sizeof(next));
		fc.__init__(N);
		mark[from]=1;q.push_back(from);
		while(!q.empty()) {
			int x=q.front();q.pop_front();
			for(int i=head[x];i!=-1;i=table[i].next) {
				#define v table[i].to
					if(match[x]==v)continue;
					if(fc[x]==fc[v])continue;
					if(mark[v]==2)continue;
					if(mark[v]==1) {
						int r=lca(x,v);
						if(fc[x]!=r)next[x]=v;
						if(fc[v]!=r)next[v]=x;
						group(x,r);group(v,r);
					}else if(match[v]==-1) {
						next[v]=x;
						for(int u=v;u!=-1;) {
							int y=next[u];
							int mv=match[y];
							match[y]=u;
							match[u]=y;
							u=mv;
						}break;
					}else {
						next[v]=x;
						q.push_back(match[v]);
						mark[match[v]]=1;
						mark[v]=2;
					}
				#undef  v
			}
		}
	}
	void open_flower(int N) {
		int ans=0;
		memset(match,-1,sizeof(match));
		for(int i=1;i<=N;++i)if(match[i]==-1)flower(i,N);
		for(int i=1;i<=N;++i)if(match[i]!=-1)++ans;
		printf("%d\n",ans);
		for(int i=1;i<=N;++i)if(match[i]>i)printf("%d %d\n",i,match[i]);
	}
}pic;
int main() {
	freopen("WorkScheduling.in","r",stdin);
	freopen("WorkScheduling.out","w",stdout);
	int N,a,b;
	scanf("%d",&N);
	fc.__init__(N);
	while(scanf("%d%d",&a,&b)==2) {
		pic.add(a,b);
		pic.add(b,a);
	}pic.open_flower(N);
	fclose(stdin);fclose(stdout);
	return 0;
}