记录编号	328647	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]篝火晚会	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-10-24 14:49:01	内存使用	0.52 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define file(x) "fire."#x
using std::min;
using std::max;
const int MAXN=50010;
int c[MAXN],n,d[MAXN],neb[MAXN][2],a[MAXN],sz,ans;
bool vis[MAXN];
void nosol(){
	printf("-1");
	exit(0);
}
void up(){
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++) c[(a[i]-i+n)%n]++;
	int mxn=c[0];
	for(int i=0;i<n;i++) mxn=max(mxn,c[i]);
	ans=min(ans,n-mxn);
}
int Main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d",&n);
	ans=n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&neb[i][0],&neb[i][1]);
		d[neb[i][0]]++,d[neb[i][1]]++;
		if(d[neb[i][0]]>2||d[neb[i][1]]>2) nosol();
	}
	int pos=1;
	while(1){
		a[++sz]=pos;
		vis[pos]=1;
		if(!vis[neb[pos][0]]) pos=neb[pos][0];
		else if(!vis[neb[pos][1]]) pos=neb[pos][1];
		else break;
	}
	if(sz!=n) nosol();
	up();
	memset(vis,0,sizeof(vis));
	sz=0;
	pos=1;
	while(1){
		a[++sz]=pos;
		vis[pos]=1;
		if(!vis[neb[pos][1]]) pos=neb[pos][1];
		else if(!vis[neb[pos][0]]) pos=neb[pos][0];
		else break;
	}
	up();
	return printf("%d",ans);
}
int enter=Main();
int main(){
}