记录编号	401826	评测结果	AAAAAAAAAA
题目名称	[Ural 1099] 工作安排	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2017-05-04 07:08:05	内存使用	0.36 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 256;
int n;
bool map[maxn][maxn],inq[maxn],inBlo[maxn],mark[maxn];
int link[maxn],fa[maxn],belong[maxn],q[maxn],l,r;
inline void bloom(int x,int y){
    rep(i,0,n) mark[i] = inBlo[i] = false;
#define nx(x) fa[link[(x)]]
    int lca;
    for(rg i=x;i;i=nx(i)) mark[i = belong[i]] = true;
    for(rg i=y;i;i=nx(i)){
	i = belong[i];
	if(mark[i]){lca = i;break;}
    }
    for(rg i=x;belong[i] != lca;i=nx(i)){
	if(belong[nx(i)] != lca) fa[nx(i)] = link[i];
	inBlo[belong[i]] = inBlo[belong[link[i]]] = true;
    }
    for(rg i=y;belong[i] != lca;i=nx(i)){
	if(belong[nx(i)] != lca) fa[nx(i)] = link[i];
	inBlo[belong[i]] = inBlo[belong[link[i]]] = true;
    }
#undef nx
    if(belong[x] != lca) fa[x] = y;
    if(belong[y] != lca) fa[y] = x;
    rep(i,1,n) if(inBlo[belong[i]]){
	belong[i] = lca;
	if(!inq[i]) inq[q[++r] = i] = true;
    }
}
inline void modify(int s){
    int x,y,z = s;
    while(z){
	y = fa[z];x = link[y];
	link[y] = z;link[z] = y;
	z = x;
    }
}
inline void bfs(int s){
    rep(i,0,n){
	fa[i] = inq[i] = 0;
	belong[i] = i;
    }
    l = 0;r = -1;q[++r] = s;
    inq[s] = true;
    while(l <= r){
	int u = q[l++];
	rep(v,1,n){
	    if(map[u][v] == 0 || belong[u] == belong[v] || link[u] == v) continue;
	    if(s == v || link[v] && fa[link[v]]) bloom(u,v);
	    else if(fa[v] == 0){
		fa[v] = u;
		if(link[v] != 0){
		    q[++r] = link[v];
		    inq[link[v]] = true;
		}else{
		    modify(v);
		    return ;
		}
	    }
	}
    }return ;
}
int main(){
    freopen("WorkScheduling.in","r",stdin);
    freopen("WorkScheduling.out","w",stdout);
    read(n);int u,v;
    while(scanf("%d%d",&u,&v) != EOF){
	map[u][v] = map[v][u] = true;
    }
    rep(i,1,n) if(link[i] == 0) bfs(i);
    int ans = 0;
    rep(i,1,n) if(link[i] != 0) ++ ans;
    printf("%d\n",ans);
    rep(i,1,n){
	if(link[i] > i) printf("%d %d\n",i,link[i]);
    }
    return 0;
}