1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=1000005;

 4 int fa[N],n;

 5 bool vis[N];

 6

 7 int getf(int a){

 8     if(fa[a]==a) return a;

 9     else return fa[a]=getf(fa[a]);

10 }

11

12 void mg(int a,int b){

13     int af=getf(a);

14     int bf=getf(b);

15     if(af==bf) vis[af]=true;

16     else{

17         if(af<bf) swap(af,bf);

18         vis[bf]=true;

19         fa[bf]=af;

20     }

21 }

22

23 int main()

24 {

25     memset(vis,false,sizeof(vis));

26     cin>>n;

27     for(int i=1;i<=n+1;i++) fa[i]=i;

28     for(int i=1;i<=n;i++){

29         int a,b;

30         cin>>a>>b;

31         mg(a,b);

32     }

33     for(int i=1;i<=n+1;i++){

34         if(!vis[i]){

35             cout<<i-1;

36             break;

37         }

38     }

39     return 0;

40 }

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=1000005;

 4 int adj[N],lk[N],id[N];

 5 int to[2*N],nex[2*N];

 6 int T,tot;

 7

 8 int read()

 9 {

10     int a=0,f=1; char c=getchar();

11     while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}

12     while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}

13     return a*f;

14 }

15

16 void ins(int x,int y){

17     nex[++tot]=adj[x];

18     adj[x]=tot;

19     to[tot]=y;

20 }

21

22 bool mt(int x){

23     for(int i=adj[x];i;i=nex[i]){

24         int v=to[i];

25         if(id[v]==T) continue;

26         id[v]=T;

27         if(!lk[v]||mt(lk[v])){

28             lk[v]=x;

29             return 1;

30         }

31     }

32     return 0;

33 }

34

35 int main(){

36     int n=read(),i,x,y;

37     for(i=1;i<=n;i++) {

38         x=read();y=read();

39         ins(x,i);ins(y,i);

40     }

41     for(i=1;i<=10000;i++){

42         T++;

43         if(!mt(i)) break;

44     }

45     cout<<i-1;

46     return 0;

47 }