记录编号	27888	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]篝火晚会	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.381 s
提交时间	2011-10-09 21:48:30	内存使用	0.74 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef unsigned short int fire[50001];

fire l;//每個人期望的左邊的人
fire r;//每個人期望的右邊的人
fire a;//目標狀態，正序
fire b;//目標狀態，倒序
fire ans; 
int n;

void printab()
{
	for (int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	for (int i=1;i<=n;i++)
		cout<<b[i]<<" ";
}

bool init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&l[i],&r[i]);
	fclose(stdin);
	
	//判斷該是否成環
	for (int i=1;i<=n;i++)
	{
		if ( ( l[l[i]]!=i && r[l[i]]!=i ) || ( l[r[i]]!=i && r[r[i]]!=i ) )
		{
			return false;
		}
	}
	return true;
}

void compute()
{
	int mt=0;
	for (int i=1;i<=n;i++)
	{
		ans[ (a[i]+n-i)%n ]++;
		if(mt<ans[(a[i]+n-i)%n])
			mt=ans[(a[i]+n-i)%n];
	}
	memset(ans,0,sizeof(ans));
	
	for (int i=1;i<=n;i++)
	{
		ans[ (b[i]+n-i)%n ]++;
		if(mt<ans[(b[i]+n-i)%n])
			mt=ans[(b[i]+n-i)%n];
	}
	printf("%d\n",n-mt);
	return;
}

void construct()
{
	//如果成環，則構造目標狀態
	a[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (a[i-2]==l[a[i-1]])
			a[i]=r[a[i-1]];
		else
			a[i]=l[a[i-1]];
	}
	//把a倒過來
	for (int i=1;i<=n;i++)
		b[n-i+1]=a[i];
	
	//printab();
	//cout<<endl;
	compute();
	return;
}

int main()
{
	freopen("fire.in","r",stdin);
	freopen("fire.out","w",stdout);
	if(init())
		construct();
	else
		printf("-1\n");
	fclose(stdout);
	return 0;
}