lxhgww最近迷上了一款游戲，在游戲里，他擁有很多的裝備，每種裝備都有2個(gè)屬性，這些屬性的值用[1,10000]之間的數(shù)表示。當(dāng)他使用某種裝備時(shí)，他只能使用該裝備的某一個(gè)屬性。并且每種裝備最多只能使用一次。
游戲進(jìn)行到最后，lxhgww遇到了終極boss，這個(gè)終極boss很奇怪，攻擊他的裝備所使用的屬性值必須從1開始連續(xù)遞增地攻擊，才能對(duì)boss產(chǎn)生傷害。也就是說一開始的時(shí)候，lxhgww只能使用某個(gè)屬性值為1的裝備攻擊boss，然后只能使用某個(gè)屬性值為2的裝備攻擊boss，然后只能使用某個(gè)屬性值為3的裝備攻擊boss……以此類推。
現(xiàn)在lxhgww想知道他最多能連續(xù)攻擊boss多少次？
對(duì)于30%的數(shù)據(jù)，保證N<=1000
對(duì)于100%的數(shù)據(jù)，保證N<=1000000
#include<iostream>
#define MAXM 1000001
#define MAXN 1000001
#define MAXNANS 10000
using namespace std;
int a,b,n,tot,Tnow[MAXM],Ty[MAXM],pre[MAXM];
int head;
int from[MAXN];
bool visit[MAXN];
int Happen[MAXN];
bool find(int x){
int mark = Tnow[x];
while (mark > 0)
{
if (!visit[Ty[mark]])
{
visit[Ty[mark]] = true;
Happen[++head] = Ty[mark];
if ((!from[Ty[mark]]) || (find(from[Ty[mark]])))
{
from[Ty[mark]] = x;
return true;
}
}
mark = pre[mark];
}
return false;
}
void cnt(int x,int y){
tot++;
pre[tot] = Tnow[x];
Tnow[x] = tot;
Ty[tot] = y;
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
cin>>n;
tot = 0;
for (int i=1;i<=n;i++)
{
cin>>a>>b;
cnt(a,i+MAXNANS);
cnt(b,i+MAXNANS);
}
int Answer ;
memset(visit,false,sizeof(visit));
for (int i=1;i<=n;i++)
{
head = 0;
if (!find(i))
{
Answer = i - 1;
break;
}
for (int i=1;i<=head;i++)
visit[Happen[i]] = false;
}
printf("%d\n",Answer);
return 0;
}