1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #pragma GCC optimize (2)
#pragma G++ optimize (2)
#pragma GCC optimize (3)
#pragma G++ optimize (3)
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse3","sse2","sse")
#pragma GCC target ("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target ("f16c")
#pragma G++ target ("sse3","sse2","sse")
#pragma G++ target ("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma G++ target ("f16c")
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int ELAS = 1<<14;
static char buf[ELAS],but[ELAS],*_p1=buf,*_p2=buf,*_p3=but,*_p4=but+ELAS;
static int bit[20];
#define gc() ((_p1==_p2)&&(_p2=(_p1=buf)+fread(buf,1,ELAS,stdin),_p1==_p2)?EOF:*_p1++)
inline void pt(char c) {
(_p3==_p4)?(fwrite(_p3=but, 1, ELAS, stdout), *_p3++=c):(*_p3++=c);
}
inline long long read () {
register long long x=0; register char c=gc(); register bool m=false;
while ((c < '0' || c > '9') && (c ^ '-')) c = gc();
if (!(c ^ '-')) c = gc(), m = true;
while (c>='0'&&c<='9') x = (x << 3) + (x << 1) + (c ^ '0'), c = gc();
return m? -x:x;
}
inline unsigned long long readu () {
register unsigned long long x=0; register char c=gc();
while (c < '0' || c > '9') c = gc();
while (c >='0' && c <='9') x = (x << 3) + (x << 1) + (c ^ '0'), c = gc();
return x;
}
inline void write (long long x) {
if (!x) {putchar('0'); return;}
register long long pos=0;
if (x < 0) x = -x, pt ('-');
for (; x; x/=10) bit[++ pos] = x%10;
for (register long long i=pos; i; --i) pt(bit[i]^'0');
}
#define maxn 100001
long long fa[maxn];
inline long long find (long long x) {
return (!(x^fa[x]))? x:fa[x]=find(fa[x]);
}
__gnu_pbds::priority_queue<long long, greater <long long>, __gnu_pbds::binomial_heap_tag> que[maxn];
signed main ()
{
register long long n=readu()+1, m=readu(), opt, x, y;
register bool del[maxn];
for (register long long i=1; i^n; ++i) fa[i]=i, del[i]=false, que[i].push(read()*n+i);
while (m --) {
opt = read(), x = read();
if (opt^2) {
y = read ();
if (del[x] || del[y]) continue;
if ((x=find(x))^(y=find(y))) {
fa[y]=x, que[x].join(que[y]);
}
} else {
if (del[x]) pt('-'), pt('1'), pt('\n');
else {
write ((opt=que[y=find(x)].top())/n), pt ('\n');
que[y].pop(), del[opt%n] = true;
}
}
}
return fwrite (but, 1, _p3-but, stdout), 0;
}
|
