1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <cstring>
6 #include <cmath>
7 #include <ctime>
8
9 using namespace std;
10
11 class Treap
12 {
13 private:
14 struct Treap_Point
15 {
16 int l,r,val,size,key,num;
17 Treap_Point() { l=r=val=size=key=num=0; }
18 };
19 typedef Treap_Point P;
20 P d[210000];
21 int root,cnt;
22
23 void update(const int t)
24 {
25 d[t].size=d[d[t].l].size+
26 d[d[t].r].size+d[t].num;
27 return ;
28 }
29
30 void rturn(int & t)
31 {
32 int temp=d[t].l; d[t].l=d[temp].r; d[temp].r=t;
33 d[temp].size=d[t].size; update(t);t=temp; return ;
34 }
35
36 void lturn(int & t)
37 {
38 int temp=d[t].r; d[t].r=d[temp].l; d[temp].l=t;
39 d[temp].size=d[t].size; update(t);t=temp; return ;
40 }
41
42 void insert(int & t,const int x)
43 {
44 if(!t)
45 {
46 cnt++;t=cnt;
47 d[t].size=d[t].num=1;d[t].val=x;
48 d[t].key=rand();
49 return ;
50 }
51 d[t].size++;
52 if(d[t].val==x)d[t].num++;
53 else if(x>d[t].val)
54 {
55 insert(d[t].r,x);
56 if(d[d[t].r].key<d[t].key)lturn(t);
57 }
58 else
59 {
60 insert(d[t].l,x);
61 if(d[d[t].l].key<d[t].key)rturn(t);
62 }
63 return ;
64 }
65
66 void erase(int & t,const int x)
67 {
68 if(!t)return ;
69 if(d[t].val==x)
70 {
71 if(d[t].num>1)
72 {
73 d[t].num--;d[t].size--;return ;
74 }
75 if(d[t].l*d[t].r==0)t=d[t].l+d[t].r;
76 else if(d[d[t].l].key<d[d[t].r].key)
77 rturn(t),erase(t,x);
78 else lturn(t),erase(t,x);
79 }
80 else if(x>d[t].val)d[t].size--,erase(d[t].r,x);
81 else d[t].size--,erase(d[t].l,x);
82 return ;
83 }
84
85 int get(const int & t,const int x)
86 {
87 if(t==0)return 0;
88 if(x<=d[d[t].l].size)
89 return get(d[t].l,x);
90 else if(x>d[d[t].l].size+d[t].num)
91 return get(d[t].r,x-d[d[t].l].size-d[t].num);
92 return d[t].val;
93 }
94 public:
95 Treap() { root=0;cnt=0; }
96
97 void insert(const int x) { insert(root,x); }
98 void erase(const int x) { erase(root,x); }
99 int get(const int x) { return get(root,x); }
100 };
101
102 int n,m;
103 int fa[210000],Size[210000];
104 Treap S;
105
106 int get_anc(const int x)
107 {
108 return fa[x]==x ? x:fa[x]=get_anc(fa[x]);
109 }
110
111 int main()
112 {
113 int i,op,x,y,a,b;
114
115 scanf("%d%d",&n,&m);
116
117 for(i=1;i<=n;++i)fa[i]=i,S.insert(-1),Size[i]=1;
118
119 for(i=1;i<=m;++i)
120 {
121 scanf("%d",&op);
122 if(op==1)
123 {
124 scanf("%d",&x);
125 printf("%d
",-S.get(x));
126 }
127 else
128 {
129 scanf("%d%d",&x,&y);
130 a=get_anc(x),b=get_anc(y);
131 if(a==b)continue;
132 else
133 {
134 S.erase(-Size[a]);
135 S.erase(-Size[b]);
136 S.insert(-Size[a]-Size[b]);
137 fa[a]=b;
138 Size[b]+=Size[a];
139 }
140 }
141 }
142
143 return 0;
144 }
