Newman likes playing with cats. He possesses lots of cats in his home. Because the number of cats is really huge, Newman wants to group some of the cats. To do that, he first offers a number to each of the cat (1, 2, 3, …, n). Then he occasionally combines the group cat i is in and the group cat j is in, thus creating a new group. On top of that, Newman wants to know the size of the k-th biggest group at any time. So, being a friend of Newman, can you help him?

1st line: Two numbers N and M (1 ≤ N, M ≤ 200,000), namely the number of cats and the number of operations.

2nd to (m + 1)-th line: In each line, there is number C specifying the kind of operation Newman wants to do. If C = 0, then there are two numbers i and j (1 ≤ i, j ≤ n) following indicating Newman wants to combine the group containing the two cats (in case these two cats are in the same group, just do nothing); If C = 1, then there is only one number k (1 ≤ k ≤ the current number of groups) following indicating Newman wants to know the size of the k-th largest group.

For every operation “1” in the input, output one number per line, specifying the size of the kth largest group.

When there are three numbers 2 and 2 and 1, the 2nd largest number is 2 and the 3rd largest number is 1.

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll __int64

#define mod 1000000007

int scan()

{

    int res = 0 , ch ;

    while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) )

    {

        if( ch == EOF )  return 1 << 30 ;

    }

    res = ch - '0' ;

    while( ( ch = getchar() ) >= '0' && ch <= '9' )

        res = res * 10 + ( ch - '0' ) ;

    return res ;

}

#define maxn 1<<18

int father[maxn];

int flag[maxn];

int tree[maxn],n,m;

int findfa(int x)

{

    return father[x]==x ? x: father[x]=findfa(father[x]);

}

int lowbit(int x)//求二进制最小位

{

    return x&-x;

}

void update(int x,int change)//更新树状数组

{

    while(x<=n)

    {

        tree[x]+=change;

        x+=lowbit(x);

    }

}

void add(int x,int y,int &fk)//并查集合并，更新

{

    int xx=findfa(x);

    int yy=findfa(y);

    if(xx!=yy)

    {

        father[yy]=xx;//少个y超时n遍

        update(flag[xx],-1);

        update(flag[yy],-1);

        update(flag[xx]=flag[xx]+flag[yy],1);

        flag[yy]=0;

        fk--;

    }

}

int k_thsmall(int K)//求第k小

{

    int sum=0,i;//初始化

    for(i=18;i>=0;i--)

    {

        if(sum+(1<<i)<=n&&tree[sum+(1<<i)]<K)

        {

            K-=tree[sum+(1<<i)];

            sum+=1<<i;

        }

    }

    return sum+1;

}

int main()

{

    int x,y,z,i,t;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(i=0;i<=n;i++)

        father[i]=i;

        for(i=0;i<=n;i++)

        flag[i]=1;

        update(1,n);

        int fk=n;

        while(m--)

        {

            scanf("%d",&y);

            if(y)

            {

                scanf("%d",&z);

                printf("%d\n",k_thsmall(fk-z+1));//集团的数量需要改变，所以n要变

            }

            else

            {

                scanf("%d%d",&z,&t);

                add(z,t,fk);

            }

        }

    }

    return 0;

}