Problem:


Score : 100 points

Problem Statement

You are given an undirected graph with N vertices and 0 edges. Process Q queries of the following types.

0 u v: Add an edge (u, v).

1 u v: Print 1 if u and v are in the same connected component, 0 otherwise.

Constraints

1 \leq N \leq 200,000

1 \leq Q \leq 200,000

0 \leq u_i, v_i \lt N

Input

Input is given from Standard Input in the following format:

N Q
t_1 u_1 v_1
t_2 u_2 v_2
:
t_Q u_Q v_Q

出力

For each query of the latter type, print the answer.

Sample Input 1

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

Sample Output 1

0
1
0
1



Sample input:
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3


Sample output:
0
1
0
1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@mt
def slv(N, Q, TUV):
    uf = UnionFind()

    ans = []
    for t, u, v in TUV:
        if t == 1:
            ans.append(1 if uf.same(u, v) else 0)
        else:
            uf.union(u, v)

    return ans


def main():
    N, Q = read_int_n()
    TUV = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, TUV), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

n,q = map(int,input().split())
U = Unionfind(n)
for i in range(q):
    t,u,v = map(int,input().split())
    if t == 0:
        U.union(u,v)
    else:
        print(int(U.same(u,v)))

Submission status: Accepted

Solution code:
class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

n,q = map(int,input().split())
U = Unionfind(n)
for i in range(q):
    t,u,v = map(int,input().split())
    if t == 0:
        U.union(u,v)
    else:
        print(int(U.same(u,v)))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.par = [-1] * size
        
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.par[self.find(x)]

N, Q = map(int, input().split())
uf = UnionFind(N)
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        uf.unite(u, v)
    else:
        if uf.same(u, v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
# import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
def IF(c, t, f): return t if c else f

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    n,q = LI()
    tuv = [LI() for _ in range(q)]

    uf = UnionFind(n)
    r = []
    for t,u,v in tuv:
        if t == 1:
            r.append(IF(uf.same(u,v), 1, 0))
        else:
            uf.union(u,v)

    return JA(r, "\n")


print(main())

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x, y = find(x), find(y)
    if x == y: return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True

N, Q = map(int, input().split())
par = [-1]*N
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        unite(u, v)
    else:
        if find(u)==find(v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
def root(x):
    if r[x] < 0:
        return x
    else:
        r[x] = root(r[x])
        return r[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if r[x] > r[y]:
            x,y = y,x
        r[x] += r[y]
        r[y] = x

def size(x):
    return -r[root(x)]
 
n,q = map(int,input().split())
r = [-1] * n 
for i in range(q):
    t,a,b = map(int, input().split())
    if t == 0:
        unite(a,b)
    else:
        if root(a) == root(b):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return x
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]


import sys
input = sys.stdin.readline

n,q = map(int,input().split())

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

for i in range(q):
    t,u,v = map(int,input().split())
    if t == 0:
        unite(u,v)
    elif same(u,v):
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91&=LRu00000KmY&$00000;4T0F0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000iWvX^00000iWvX^00000001BW000000RR911^@s6FdYB@00000FdZNO00000FdZNO00000=mG!$00000Pz3-000000001BW000000ssI21^@s6NF4wG00000NF5*m00000NF5*m000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa402crN0000002crN0000002crN00000TmS$700000TmS$7000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4FdYB@00000FdZNO00000FdZNO00000&;kGe00000&;kGe000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$-2Q{F3!MtR^^RX;-n4k4_`a)!0ssI26aWAK0RR911^@s6000mI0RRL56aWAK000006qpP{bCw4J000000000000000000000000000000ng9R*5&!@I00000000000000000000x&QzG5&!@I00000000000000000000x&Z(HA^-pY00000000000000000000ZU6uP5&!@I00000000000000000000p8)^>5&!@I00000000000000000000tpNZ45&!@I00000000000000000000vj6}95&!@I00000000000000000000KLG#$5&!@I00000000000000000000jsXAw5&!@I00000000000000000000@c;k-5&!@I00000000000000000000MF9W+5&!@I00000000000000000000RR9105&!@I00000000000000000000+yDRo5&!@I000000000000000000009{>OVAOHXW00000000000000000000bpZeX5&!@I00000000000000000000$pHWW5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000f&c&j5&!@I00000000000000000000T>$_95dawgKp-Fh000005CH%H00000c>n+a5dawgU?Cs?000007y$qP000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q*Sw6O<!qlb7gXLNn%AsQd4hKUjScPPE%=eb45~V0AE^DbTeaVZUA3ePE&L^X>W61VqtS-G)Zo0bVM;lb^u>mQ*<#mUte@+a&LEEVqs)oVQg$~V|D;vT4Zccb^u>mPE&L^X>W61VqtS-F*S2}Zew3}X>@2`b97{BZ$)ANUtec<cwca3a&vEPVQgu1d0%!g0AE^DbTKwxUvG1Ca%Ev{UukZ0WpZ>$V^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9kP)k!YUu*zhT5fl30AE^8Q*=0KZ*yN_VRL0PNp5L$Lor2m0AE^DbTngcb#wr1X<}z%V_$PFb8jv&0AE#ZcWG{9Us7drb!}w;Y-wU+E^}`#HUM8=b97;2YhPn%YhPwzX>0&rUtx1|WpZ?1W?^Y;0AF8Ycwt{*bY*yHbO2vpV|Za-W@&C=Y-xIB0AF8hX<}nvb97;HbYE>@X>I^VLqlIPE-(N`Oi4mRUotK<07pzoLPK9NE;24P07F<<K|)DiF)lLzM@&gVLs(c}GcGhPIRHmYNkT(dSYI<PGynhq0ssO40{{X50{{a60ssO41ONp90ssX71^@s62LJ;A000000ssO40ssI2000000RRC2X8`~J5C8xGAOHXWP$qc`000L7+W`Oo000000RRF3gaH5m5C8xGFaQ7m6lrM<000C4;{gBw5C8xGbsA|200093?EwG)000000RRI40RR915C8xG00000)30j<000I6`2hd`5C8xGiGL{q000F51Ofm65C8xGbSaVu000625&{4K00000FdZNO000002mk;800000&=UXv00000I2|AW000002mk;800000pb`K800000Kph|e000002mk;800000kP`p^000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s60{{R30000000000*dHJO000001^@s64gdfE0000000000;2$6W000001^@s65C8xG0000000000=pP^e000001^@s65dZ)H0000000000@E;%m000001^@s65&!@I0000000000_#Yqu000001^@s66951J00000000005Fj7`000000RR914FCWD0000000000Kp-Fh000001poj56aWAK0000000000U?Cs?000001poj56#xJL0000000000a33H5000002LJ#70RR910000000000cpo4D000002LJ#70ssI20000000000fFB?L000002LJ#71ONa40000000000h#w#T000002LJ#71poj50000000000kRKob000002LJ#71^@s60000000000m>(bj000002LJ#72LJ#70000000000pdTOr000002LJ#72mk;80000000000s2?Bz000002LJ#72><{90000000000upb}*000002LJ#73IG5A0000000000xE~+@000002LJ#73jhEB0000000000z#kw0000002LJ#73;+NC0000000000$R8j8000002LJ#74*&oF0000000000NQ3MMNQ(v46(9geg}`(I|IkQ-#0bLx|1~-lAOQa*JQW}S4<A4P|0OyVAOL6p0002#;Q#;s|0OaNAOL6q0002#(EtDc|0OCFAOL6r0002#!2kdM|0N<7AOL6s0002#u>b%6|0Nm~AOL6t0002#p#T5>|0NO?AOL6u0002#kpKVx|0N0)AOL6v0002#fdBvh|0MzyAOL6w0002#aR2}R|0VhqAOL6x0002#VE_OB|0VJiAOL6y0002#Q2+n`|0U`aAOL6z0002#K>z>$|0UuSAOL6!0002#F#rGm|0UWKAOL2N0000000000L03UmG5<kTK~z;!NP+B_0001FNQ(p|C;$KeNQs0bhyVZpF~H~*|Ns9;jdUbDNR2%y79apf#{~u#AOHXW002ylbR<wrjbtQD=>Puz|45B=BtS@s$LR9@|Nls1bR;}UjeZDBiQ-7dL?l=M0000;$3!Gx00000NXJAZXaE2J07%C~Bya!#002nGL?n0s0000;$Alz+000000001qbR<y6L?lfA|NsB!><9n=NMm#)P)LnzBuGh(ejvw0BuD@N002md>gdi0004_bBtT4!Y$QZXjeI0KjZpuEz=>2OKo5nh0002#W&r>I4<A4Ph0+g*a|8eYi*zJViP-nhIo1!K!NKSsguxGlTLb_AIo=PBQv?72NQ-<VSV&{aiv*8@`2P=utN{Q3Io=PBeE|RfNMp;31doIG{||-j0RR9w({wmUi*zJ#NMpiGW5Y<n-~vvK6omi)002yl3<g1q2|_yzhI|nZh2;SN0E58+Oo`Bm(?N*|i5v%uL?l3sQ2&L%iBu#&4}`z~002mhJ--wn08EMQ=%@Yv|451MNQuYjoc;g*Oo`@5iO1-X{r~@qL?lFuTqI13R3u1+zz>8a|NsAm(hrDv0{{SvbR<xT*!R%E=pQ-O51+w=!4HIC0{{Ry^AC+#0{{R>i+m(lNMp*21doIG{||+M0000;W6O&KkAwLC4~6mo001%eNR2%i6CeON(?AcD#^|2?|NpuH0000?iT+55$Hqh?I|}G&{r~@qL?l3sQ2&L%iBu#&4~0Pg|Nl&h_vj7>001$-NQ;alhyVZpWJog%B`5#@01t)V1ONa?fy9^q003KEL0myyL0&;$!w(+-ImUh^g}`_rOk==8ixh{0`u`7wzyJUMiNc8#kBf99P&wWYk5>Qx|45Au00{s9NR2gp2mk;`jXiz{006op0002!i2VQm4<Cd800000g}`{#ImUj`Ok==8ixh{0`u`7w<NyEwiNc8#kBf99Q0XrI|Nmw#4<Cd800000g}`{FIq-d<Ok==8iyVi8`~MGxj{pDwiNlE;kLm3G|NmwWA4C8Eg}@JpdH?_aImQo;asU7SOk==8iyVi8`~P)4iNlE;kLm6G|Nl&h(23LO9RC0Rh0+g*N&o-<Io1!3LI3~%Ok>JIiv*8@`2P=u^8f$<LWvZI=^6k3|ApHRh#>#}|2f_dju`*{|4d`cLW=~CgZTdsg`xle078izhwGn(+YgBP{{R0u^AC;k{{R0>W6MH|1doIG|8-YFi5!RNPXGV^Io1!3)&Bqgh0+g*&Hn%YOk>JIiv*8@`2TeYLWvZI>G}Tu|2f7Fj<Ej!|AoL0h^YSm|43udM2j4kL4*7M4}}N;002UX1doZr>&}J14~U2U|NlAg4~>8R|Nls1*hGsQpFxBB{||++0000&i3E>{!|Q-K#t)8O{{R1lzz>L4{{R0-W7tHC9G^jh`~P)bLWu;AiNonO|NsAmzz>Kv{{R0u#t)7z{{R0-W6(s49G5|Z`~P(dLWu;AiNfjS{{R0)h1(B^4gUZCL^<9Mjs*Vy|4n1lLW=~KgZTdsg+KuS07Qu#mqdx!>&iqq-VcuA{r~?(h1(B^+5P|jO=HtSiv*X0`2P=uhyefqM2Q@qM2XnxbpQYVK{@jejkNv$|3!t{4~VP%|Nl*6(?W{`mxK8K4~5GC002aZ9G^sq*y$nv|Nlfe-Vct3{r~?(h1(B^ef|IcO=HtSiv*X0`2TfEM2Q@iM2Xnx&i?=ZNR16e1^@s^jWyy0002mhJ@*9w0J<vx008Li`Tze&jSXf7002mhHNyn}07#8J*aZLpx-b9$0O-#7|NlA04~`%G|Nn)+4~Q52|Nl&5*g}gmpM(DYbW2Q$_e_agBq&UYR3sosiBu#QOo>b+5KM_gBnU`}3?%3c0{{R>i+m(lOp9D3C`^k~Bp^tOR3sQoi%cXCOp8P$2uO<zBtnS<pF)WQmqCfc=|lhj|2f7Fj;#Fu|AoL0h@|}g|4d`pLW?w?gZ}??OH7IPOo?11C`^e|Bp^tMR3sQoiA*FAOo>D!2uO(xB<Pv~002mfd?Z**i(DiqOp8<`AV`Z;Bp6JKOe7FYi$o*{NQ(?4LWu;QLWu;IL5aiZP5%G?ImQo;IsE_sg}@JpG5r7kOk>zWi!`5u{{M7IOo{hQiCiQoOo>z^AWVr&Bp6JIL?jSMiA*F2i4-L0C;|WgNQ-<VSWJstBq&UaR3sowi%cXKOp8P$5J-zmBnXQXBtnS<pF)WQmqCfc=?DJ*|2gmvjmZ1||AoL0h`{^*|4d`pLW?w?gZ}??Nlc0NOo?11C`^e|Bp^(QOe7dgi9{q2NQq1&2#FLV=(hm?07#2`Bv?#~TqGz=i&P{aOp8n;7)*;qBoIi8Oe6@46eL241fN2Q1eZaH!|BBR|NrPg`2YV*iT6l}!{`PA002md-{@}m|Nlsfd?av4iNi>R|8xcD{P+L=NQ-<VSV)Ecblm9e_y7Ov)sSW`4<Cd800000NR2(x4<G<YgX{?C5cvQ9NQ*r|4IltWjTK4_AOJ{>HM9>P07!$x2<f8t|Nmx?G3`l-(OyW2;z)z!@K97tjRi^r002mh4buVu07#8J4EX>5{}tv8AOQ3aA4C8ENR2%a4IltjNR0&v4IltWIrvD4<#ZWHiv_w2AOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2(w3?KkVjWx;)AOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(u53?KkVg}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIZ<3AOHY$FGzzuFAN|6098nd<#Y^4i#=KlAOPq+_y7OsNdN!;#s#?!AOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8Eh4w*IRa1Cfiw{VN{W<Y|R7i_|2uNezNWtR*NR1R9ivolA|8)sliSS)PT*GFNg}`_*Il+D{Ok?0ei!`T${{M9hiN=WniSS!pL0rR-NQv+0sQ>@}NQ+enLWu;TNCDdG-$;!ObOHbXNR2h|0RR9<jXm-K006op0002!{Pq9;W-bpOga7~l003r?Q%H&XNQ-|UNQM7&1?c|u|Nlsfdk9E{|8xyo>F@Rb{|_I400000Tf=4#A4C8ERZ~cb`$&WA7)XmhNQ*-dNGbS8!T175ImQo%fB*mhOp8MZivmoE!AL3jNWu96NIA}TD@cX*bQVa7`ACWKi2+E1!30Qy>H&51NR2$VNQrw0NQ1-}TV2BsA4C8EOgYDN5Dy;!i3do7#{@|^_;vM*0!S&&Oo_oriSlNUi2+E1!30Qy>H&51NsR=sNQpxTNQ1-}TV2BsA4C8ENQL%vYe=~N|NsC0|NlQoImUNmNR2GD00000NQqP=2uO)EBuI(x=p*(2|455eBnU{0G$c%o1SpFNNQuIbi3&)A!URZz?g4f5NQ*m2h5ty215AlS2uz7X5OkGDgTxqHUFp{J|NmwWA4C8EF~CJJ!0XuPboBrK4<A4PL03UmNr~4%RY6otjU`?OAOKZJjV)#eAOKTAiTz25_Dm_|NQ3MMNWuLB=oj?=|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF3ZDDC{E@NW=Fd#fVAb21qCLnkqJRojg00000Fd#fVAb21qCLnkqJRojgASNatFd#fVAbB7rCLnnrJRojg00000000000000000000000000000000000VsCG3AXRQ@Z*E3uZe%(-b75^|C~0nVEFfuabSVG;X>N2NRc>i-ZboTtWI8%>Z*O!cX>N2W0000000000c5i89AXRQ@Z*E3uZe%(-b#7^NWhiNGbSxlgZgeRC0UHB5TmS$73IG5AAoKtKr~m)}@bmxw&;S4c0QCR=qyYc`p!@&-_yGU_(EI=YcmMzZ;Qasp=l}o!aQ*-PAOQdXp#A^<Kmh;%!2bXL5CQ-IF#rGmSONe5000006aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|SQ2YP?D*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|SaPt5E&;S4c01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)81w)C2mk;80000000000GynhqTmS$7@caM&ga7~l07MQDi~>Op7={Bu4j_XBVhRozLk<u^4hTaFTM7;sK@Jc?4hTXE8~^|SlmGw#Nc{i*DgXcg06`8Ag92L$4hT#OK@JE2KmY&$v;Y7ASp5J09033T06`8Ah5|tj7=r^x4ln{w3Jw@S4iG^O2u2Hd3Jw@S4iG^O2u2G6V+sx!K@Jc>4hTyN8~^|S000000eVnOQUC#X5C@xi2Ot0&8w>{skO2SyPyhe`Bme*aRPz7-l?MO-1iJtL074EBj{-st7>)x(4j_#LLJla51wjrlh6X_nID-dA4$uJuZvqMqI6)3DK@KQF4j@7f7(xyZLJkN-3jhEB6aWAKYykiOp!xs*E&u=k080)KUJeKVL;wH)gaH5msQmx`WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xG%mDxZ(ER`Z0ssI20000000000|Nj9NCO7~9uK^?S4gjPBqXFLz0PPM1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000&=UXv00000pb`K800000kP`p^000000RR91000000RR91000000RR9100000X8`~J000000RR9100000gaH5m000003;+NC000002nqlI000004FCWD00000G!_5=0000082|tP00000FdZNO000008vp<R000005C8xG000008UO$Q00000Kph|e000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000&;$Sg000001^@s600000zybgO000003IG5A000009s&RW000003jhEB000007ytkO000006#xJL0000000000000000{{R300000SRWt&000000ssI200000AOQdX000006aWAK000002LJ#7000007XSbN00000=m-D+000002LJ#700000um=DD000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000AO`>d00000|NsAQ000000{{R300000@c;jB00000?gjt=00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000NF5*m0000000000000000000000000HVOa$00000MhXA`00000Rtf+B00000W(oiR00000b_xIh00000h6(@x00000mI?p>00000rV0Q600000wh90M00000#tHxc00000)(QXs00000<_Z7+0000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j9&;$Sg000000000000000000000{{mA?gjt=000000000000000000000{{pBAO`>d000000000000000000000{{sCum=DD000000000000000000000{{vD=m-D+000000000000000000000{{yE2nqlI000000000000000000000{{#FAPN8g000000000000000000000{{&G@CpC`000000000000000000000{{*H01E&B000000000000000000000{{;IG!_5=000000000000000000000{{>JKo$T1000000000000000000000{{^K02crN000000000000000000000{{{LU>5)Y000000000000000000000{{~Ma2Wsq000000000000000000000{|2NFdZNO000000000000000000000{|5OKph|e000000000000000000000{|8PNF5*m000000000000000000000{|BQSRWt&000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000002><{90RRvHz!m@i0000082|tP00000H2?qr0RRvHpcViC000009{>OV00000VgLXD0RRvH;1&P?00000AOHXW00000kN^Mx0ssyGpb`K800000E&u=k00000qyPW_0RR~Qc_JVH000000RR9100000vj6}91OV~>00000000000000000000z5oCK0ssyG022TJ000000000000000zyJUM0ssyGKobA}000000000000000(*OVf0ssyGkP`p^000000000000000=>Px#0RR~Qcp@MG000000RR9100000_y7O^0RR;MKph|e0000000000000009{~UW0ssyG&=UXv000000000000000D**ri0RR*LFdZNO000000000000000vj6}91OV~>00000000000000000000N&x@>0RR#JY#9Im000000000000000000001OV~>00000000000000000000SOEY4000pH02crN000000000000000YXJZN0RR>NNF5*m000000000000000bO8VW000yKKph|e000000000000000g#iEn000yKFdZNO000000000000000m;nF)0RR^OSRWt&000000000000000t^oi5A^;8ma1;Ol00000DgXcg00000zySaN5C9ke7$6`3000000000000000f&%~mAOIKu03aX$000000000000000#{mEU5daVXKo$T1000001ONa400000)&T$j5&!@I00000000000000000000`~d&}5&!@I00000000000000000000D*^xjA^-pY00000000000000000000p8x;=5&#YW01E&B00000l?MO-00000M*;u<5ds(h2p}K;000000000000000R00415&!@I00000000000000000000YytoP5&!@I00000000000000000000hXMcqAp#fx5Fj7`000002mk;800000e*^#k5&#bXG!_5=000000000000000qXGZ`5&!@I00000000000000000000y#fFL5&!@I00000000000000000000h64Zq5&#YW&=LRu00000D*ylh00000(E<Pf5&!@I00000000000000000000<N^Qy5&!@I00000000000000000000$O8ZX5&#PT2nqlI00000000000000000RI35ds(h7$6`30000000000000003<CfF5&!@I00000000000000000000X#)TN5dawgKp-Fh000005CH%H00000fCB&k5C9ke03aX$000000000000000fB^si5C9nffFd9O000000000000000jRODx5C9nf7$6`3000000000000000nF9a-5&!@I00000000000000000000z5@UN5&#YWz!d-h00000WdHyG00000&I14d5&!@I00000000000000000000_5%O_5&!@I000000000000000000007X$zRAOHXW00000000000000000000GXwwt5&!@I00000000000000000000O9TJ_A^;8mpcDWA000009033T00000bp!wa5&#YWFcts+000000ssI200000g#-Wq5dawgU?Cs?000007y$qP00000n*;y=5&!@I00000000000000000000x&#0KA^;8ma1;Ol00000DgXcg00000%me@cAOHXW00000000000000000000+XMgrA^;8m;1d7<00000ga7~l00000@B{z=AOHXW000000000000000000003IzZF5&!@I000000000000000000000BvDuZZ2bE0AE^KPB~R>X>V>uX>MdRa&K>RMQKGbIbUB;Qbkl$Szks~PD4~lPflN70AE^KPB~R>X>V>uX>MdRb75^|MQLe8F*#pfP*O!yR9Rm}RZc@xNl#8+UjScPT247tZfS3BMrm$jHFa)jbY(?pX+<$PUtdsCMO0K-Uq)3<LsUsmPG4UDUq?(&LP1PlUvqV0UrAqWVQFpvUs_XiOgLX(X>Vz6X><T%a&&Wab!KKRV*q4ja%E>}b97~LUvzC>V{C73Wpe;uUu17zXKZg`VQgPybZ>HVUtx840Ap`$aBO9CWn?ZlHaR!|UteTzUuSG@Vqt7wWOQ$Gb6;U~cwc5|ZfRd(a&lpLUuAA|a(Mt|a$#*{Uu1P{ZFvA+UuJS)ZDn6%b!}~VUukY>bYEd|a$$L2Wo~qGc>rHuMp8jdMPEfuL|<P3UtdQ~RbNF&Uq(_vO+{ZwL{b1>L|INjO-VxlUtei%X>?y<a&lpLUuAA&0AF8eZfSI1VRCX|d0%sMVRCc;Uq?(&LP1PlPew*lMO0r@K|)MLUjScPPB~R>X>V>uX>MdhGDUU(Uu9%rbYTErNl#yMbYy96Uv+b3WB^}UQ*<#mUte@+a&LEEVqs)oVQg$~V|GA5M@&gVLs(c}GcGg$Us_I6bU0~mb6;X%b7e6#b9ruKUw3JAXkT-5WNB|jVn9GgOi4mRSXf^(E;ImNUt@S-UuJ1;VQgu7Wk5hjOi4mRUotK-E;RsOUu1J{Uua=&WNc*sUs_I6X>xN#QfWXyM@&gVLs(c}GcGg$UteK!b7gXLUuI!xY(PLqOi4mRUotK-E;Rr|S1xj8W-eb}XLxvDaAk6HZ*F01X>@sCb}#^6Ut@S-Utx4*cxiM%Ku1hTLPK9NE;24P0AE^UY*2PUKu1hTLPJ<sUo$Q=0AE^ecWppGM@&gVLs(c}GcGg$Ute={VPk7wV`yt%W?^Y;KtM-KNkT(kGA=X#Utd&BLtjNsL|<P3Us_XiF*aXcZ*z2VWnpb!X>N06a&$>!Q*<#gV`yP=UvzR|X>@Z*V?{+$Q*<#iVqtS>V_$D`baG{3ZAnyLR4`vfQ#M~vOH(snY(PLqOi4mRSXf^(E;KGV0AE^DbTngcb#y>LM@&gVLs(c}GcGg$UteTlbYWj}bYXII0AF8Xb8}yFbYXII0AE^8Q*=0KZ*yN_VRL0PNp5L$Lor2mKtM-KNkT(dSYI<PGyq>;Y-wU+Ut@E1UukY>bO2vkPE&6=Urk?WZgXXFbV*`GMN(65R9`?qM@&gVLs(c}GcGhPIRIZ@XLxvDaAk6HZ*F01X>@sCb}&FdLs(crLP=jSE;9gMNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnRc?1_Ze(9lWpj0HWk5hjLqlIPE-(OJT251RHg;uWbZ>G=X;WcIX+=dbG+#|$W@&6}Utx1|X=iRlZBk2V0AF8hX<}nvV{>(1W@&C|0AE^DbTeaVZa_dsOi4mRSXf^(E;ImNUu<b&V_$Q0VRCd|ZDDC{KtM-KNkT(kGA=SMH2_~)PB~R>X>V>uX>MdhF-3L&Utec!Z*E_6bYXIIUta)UT247tZfS3BMrm$jG;(imbVX?ZUrAI=Uvgz<X>)XCa#T%2Y;SI5RAFLlWdL7VPE&L^X>W61VqtS-G)Zo0bVM;lc0fQ!Oi4mRSXf^(E;IlDE^~QpbYWruE^~BpbYWruE^}yebaHfIVgN2_ZggdGZ~!iDZ**lYK|)C_bYW)zE^cphWiDrKbuMCcX>4RIX=DH{XKr;aXkl|`04`*CZgY8U04`*CZgX^U04`^4buM;ga&u{KZU8Q4ZgnnpWpZ<AZ*E_504{Q6Y+){Bd2RqMa%F5`E^usg04`~6X><TCaBOrgXK!=>E_7vhbO0`9X>Mr%E^=>VVRT^tE@fz6W^!R|WnXAyasV!6XkTV>VQpmqE@xw7UuAe>WpH#~bYWs_WdJT|ZfSI1VRCX|c>peEX>Ms>VRCX|c>peCd2V5CX=4B`WMOn+04`#4a{w-5Z*6U5Zgc<u000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO000005CQ-I000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000&;$Sg00000&;$Sg000009s&RW0000000000000000RR91000000000000000UH||9|NsAQ0ssI200000?gjt=00000?gjt=00000EC2ui000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000AO`>d00000AO`>d00000kN^Mx000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000um=DD00000um=DD00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000=m-D+00000=m-D+00000AOQdX000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s6000002nqlI000002nqlI000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000APN8g00000APN8g00000&;S4c0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000@CpC`00000@CpC`000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s60000001E&B0000001E&B00000G7A6z0000000000000005C8xG000000000000000qW}N^0RR911^@s600000G!_5=00000G!_5=000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000Ko$T100000Ko$T100000zyJUM000000000000000AOHXW000000000000000u>b%70RR910ssI20000002crN0000002crN00000TmS$70000000000000001ONa4000000000000000zW@LL0RR910ssI200000U>5)Y00000U>5)Y000005CQ-I0000000000000002mk;8000000000000000$p8QV0RR910ssI200000a2Wsq00000a2Wsq000008UO$Q0000000000000000RR91000000000000000+W-In4gdfE0{{R300000FdZNO00000FdYB@000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000Kph|e00000Kpg-8000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000NF5*m00000NF4wG000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000SRWt&00000SRViY00000r~m)}0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000Kp-Fh000007$5)u00000Kmq^&000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000SO@?B000008~^|SF#rGn2mk;8000007ytkO000002><{90{{R300000000000000000000peO(U00000F9iSq0000000000000000RR910000000000000005dZ)H0{{R300000000000000000000&n*A|000005CH%H0000000000000000RR91000000000000000"

open("./kyomu", 'wb').write(base64.b85decode(exe_bin))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
# Reference: https://note.nkmk.me/python-union-find/
class UnionFind:
    # if x is root: self.parents[x] = -(the number of the group nodes)
    # else: self.parents[x] = the parent of x
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # return the parent of x
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return x

    # merge the group of x and the group of y
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # return whether x and y in a same group
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    from sys import stdin
    input = stdin.buffer.readline
 
    n, q = map(int, input().split())
 
    uf = UnionFind(n)
 
    ans = []
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            uf.union(u, v)
        else:
            if uf.same(u, v):
                ans.append(1)
            else:
                ans.append(0)
    
    for i in ans:
        print(i)
 
main()

Submission status: Accepted

Solution code:
# Reference: https://note.nkmk.me/python-union-find/
class UnionFind:
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return x

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    from sys import stdin
    input = stdin.buffer.readline
 
    n, q = map(int, input().split())
 
    uf = UnionFind(n)
 
    ans = []
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            uf.union(u, v)
        else:
            if uf.same(u, v):
                ans.append(1)
            else:
                ans.append(0)
    
    for i in ans:
        print(i)
 
main()