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:
# Implement (union by size) + (path compression)
# Reference:
# Zvi Galil and Giuseppe F. Italiano,
# Data structures and algorithms for disjoint set union problems
class DSU():
    @classmethod
    def dsu(cls, n):
        return cls.InnerDSU(n)

    class InnerDSU():
        _n = 0
        # root node: -1 * component size
        # otherwise: parent
        parent_or_size = []

        def __init__(self, n=0):
            self._n = n
            self.parent_or_size = [-1] * n

        def merge(self, a, b):
            assert(0 <= a < self._n)
            assert(0 <= b < self._n)
            x = self.leader(a); y = self.leader(b)
            if x == y:
                return x
            if -self.parent_or_size[x] < -self.parent_or_size[y]:
                x,y = y,x
            self.parent_or_size[x] += self.parent_or_size[y];
            self.parent_or_size[y] = x;
            return x

        def same(self, a, b):
            assert(0 <= a < self._n)
            assert(0 <= b < self._n)
            return self.leader(a) == self.leader(b)

        def leader(self, a):
            assert(0 <= a < self._n)
            if self.parent_or_size[a] < 0:
                return a
            self.parent_or_size[a] = self.leader(self.parent_or_size[a])
            return self.parent_or_size[a]

        def size(self, a):
            assert(0 <= a < self._n)
            return -self.parent_or_size[self.leader(a)]

        def groups(self):
            leader_buf = [0] * self._n
            group_size = [0] * self._n
            for i in range(self._n):
                leader_buf[i] = self.leader(i)
                group_size[leader_buf[i]] += 1
            result = [[] for _ in range(self.n)]
            for i in range(self._n):
                result[leader_buf[i]].append(i)
            return [r for r in result if r]


N, Q = tuple(map(int, input().split()))
tuv = [tuple(map(int, input().split())) for _ in range(Q)]

dsu = DSU.dsu(N)
for t,u,v in tuv:
    if t == 0:
        dsu.merge(u, v)
    else:
        if dsu.same(u, v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${@o!EWOq5WPprKa5;8O17@4)XOT8uY0VN^KMlU7$>M05QEe0e*F%ZcHOPY#SHJwd(1Oepbe!d8B2Sx(w!!G!d~6ntXEe{$T(#ujZfM{>c!cQD3o^zDM^<^XT6eESaTHNHJ!b?@4gE%32%c`&#XwoO=EcFo`|AqWd~K*dpP>ZX;NoY&;1W+=>zx@Wsos5-moG15!g+I0LqNP$HWreen7els^sH4VJ_DzrEviKoiI8m^hWrQgiOk7jJK5R+g@mzx^oB(I5{HmEC@}-n*DkOyowsTDJzM98|rypTy2d@;CBDcay?=^VL@bD4vq^#o&$*ez9Qt>qU1ZwjQ=1qfAAA9&;GN17=3(%6Gs|o%dACg9VKo2duF7h8(IjFTZS54);5d%LkovRnOc}yxU5&DciUX+Yu&W4VcO=ft3*x)zG>*e;Y*3>fsuiKmSGKu{0?z@*wrW(LbDWGY}jLSsS}z367)UXEwk_Dl=EFG4f*XX81qnB_m^W;-IdS_pBw%Hson8D")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR915EcLc00000KmY&$00000Xg&Y{0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000_8kBK00000_8kBK00000001BW000000RR911^@s6Ff9N800000FfAYe00000FfAYe00000=mG!$00000h@S`m00000001BW000000ssI21^@s6NG$*W00000NG%`$00000NG%`$000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa41RDSV000001RDSV000001RDSV00000YybcN00000YybcN000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4Ff9N800000FfAYe00000FfAYe00000&;kGe00000&;kGe000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$f+WhT(AEf#l#&{{e<mPwVOMT?0ssI26aWAK0RR911^@s6001BWfB_Hy6aWAK6#xJLDIJU)XH{Vk000000000000000000000000000000Z2$lO5&!@I00000000000000000000GywnrA^-pY000000000000000000003jqKC5&!@I00000000000000000000836zQ5&!@I00000000000000000000{r~^~5&!@I00000000000000000000h5!Hn5&!@I00000000000000000000q5uE@5&!@I00000000000000000000=Kufz5&!@I00000000000000000000E&%`l5&!@I00000000000000000000r~m)}5&!@I00000000000000000000LjeE)5&!@I00000000000000000000jQ{`u5&!@I000000000000000000009{>OVAOHXW00000000000000000000&Hw-a5&!@I00000000000000000000O921?5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000CjkHe5&!@I00000000000000000000RR9105&!@I000000000000000000005&-}J5dawgATS^R000002mk;800000_y7O^5dawgFfbqh000002mk;8000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q*=0KZ*yN_VRL0PNp5L$L@`Bn0AE^DbTKzyUvy}4Z+Bl}VPs!nY;131b^u>mWNc7&0AF8ccz9oMWpZ<GZeeU`ba`KPFaTd#Zg*_}Us_I6bU0~mb6;X%b7eG1ZfSHwF-3L&Y-wU=V`E=)E^}`#F#umxZg**JWM5Kcb9HTH0BmVuV=i-VE;ayPUvqR}V{2byXlq|)VQFjtb97{BZUA3jV|Za-VRU79X><T>Wo>h1bO3X7WN&qJ0AF8iWo>P5c4c2<XlnpwcXDZTWdLS!Wnp9hUteQ*VP9rxZeeU`dSw7@Wo>P5c4YuxUu<b&V_$Q0VRCd|ZDDC{07pYZUo$Q+07F<<K|)DiF)lLzM@&gVLs(c}GcGg$M@&gVLtip3Gyq3TNkT(kGA=VNGyq3TNkT(kGA=SMH2?qr0{{X50ssU60ssR50{{g80ssR50ssa8000L70ssI2000620{{X50ssI2000000RRC2zyJUM5C8xGAOHXWP$qc`000L7T>$_9000000RRF30RR915C8xGFaQ7m)30j<000I6WdQ&H5C8xGbSaVu00093Z~*`S000000RRI4-2eap5C8xG000006lrM<000F5d;tIe5C8xGbQx(0000C4h5-No5C8xGbsA|200062k^uk!00000FfAYe000002mk;8000005ElRd00000I4vLm000002mk;800000AQb=r00000KrJ8u000002mk;800000&=vpy000002rwW3000002mk;8000002rwW300000&@UhW000001^@s60ssI20000000000*e@Ue000001^@s64FCWD0000000000;4dHm000001^@s64*&oF0000000000=r14u000001^@s65C8xG0000000000@Gl?$000001^@s65dZ)H0000000000_%9#;000001^@s66951J00000000005HKJB000000RR913;+NC0000000000ATS^R000001poj56aWAK0000000000Ffbqh000001poj56#xJL0000000000a4#SL000002LJ#70RR910000000000crPFT000002LJ#70{{R30000000000fG;2b000002LJ#71ONa40000000000h%X=j000002LJ#71poj50000000000kS`zr000002LJ#71^@s60000000000m@gmz000002LJ#72LJ#70000000000pf4Z*000002LJ#72mk;80000000000s4pM@000002LJ#72><{90000000000urDA0000002LJ#73IG5A0000000000xGx|8000002LJ#73jhEB0000000000z%L*G000002LJ#74gdfE0000000000$S)uO000002LJ#75&!@I0000000000NQ3MMNQ(tkCLjPvg}`(I|IkQ-#0bLx|24WLAOQa*yd@w24<A4P|0TL5AOL6p0002#;Q#;s|0S{|AOL6q0002#(EtDc|0Sv=AOL6r0002#!2kdM|0SX&AOL6s0002#u>b%6|0S9wAOL6t0002#p#T5>|0R+oAOL6u0002#kpKVx|0RkgAOL6v0002#fdBvh|0RMYAOL6w0002#aR2}R|0Q}QAOL6x0002#VE_OB|0QxIAOL6y0002#Q2+n`|0QZAAOL6z0002#K>z>$|0QB2AOL6!0002#F#rGm|0P-_AOL2N0000000000L03UmNR2%e!XyAeRY6o$Q%HgAhyVZpNR4zPFi4GDBtT?Hiv%So0000;i9{rLF~I0K4gdg1jdUb5NR2(+!6X3aC=LJsNMm#)Fi4G5Bs@rsdk9F!L?lQ60000;$3!Gh00000NXJAZSO5S307%C~Bwzpl002nGL?mbc0000;$3!G>00000iF71D$3!GN|NsC0NQqn|5a_N9002m1bR<AXjZ`E!NR4|S$3!GJ00000=#vZp08EWN{3IX%OpPT~!6X1pjkf>*1OSUfBs7gs|AoMbR3tPHgjxas08EQ5Ji#acNQ*Ts!6*PsIqnaHlmq|(54Hw83UmZKAayB7jYa_vA4C8ENQngr!6*O^wh%~(#z=#}0f71-bn1Zm3UuX3IrVhBNR37mNjb$2hLZyT07#1!+`uRR54Hk4Ef0jr0ssI!FAt9T1poj=F~CTJ!T~YuNQu@+i50fMC;*L2tpG@kQUQbD4~;BH54J-8JTHIXMTEd~0{7iXIrR^OXaoQN54Hw8Aan#g3Uw(+jYa{GNQnh`z$gF@wh%~(#z=#}0f71-bn1Zm3UuX6IqnaHfdv2nNR37mNjb$2hF=2!07#1!NWdrn54Hk4Ef0iU0ssI!FAt7z1poj=F~CTJ!T~Yc4<A4PNQu@+i4`8eC;*KNn@EjP0fXQVjT}f1wnG0rFMr`hgurwH_uEW4?hk}11ONaJwgx;PbObyKbuvheMge9n4<Cd800000NQnj6zbF6?wh%~(#z=#}0f71-bn1Zm3UuX3IrR^O)dT<lNR37mNjb$2hW7yg07#1!sJ|!x54Hk4Ef0ik0RR9zFAt8|1ONar_DF-m0Yx$G4<A4PLyb(W0E6HUNQo7BzbF7mgTetsjVwqHwnG0rFMr`cg!Xg;LHFHAi&P{?NMp-|?TZA84~3=x004vd{||))1ONa@W9^Fss)P9d4~5nP002Qb-4BG{{r~?+i*zJlNMplEWBo|M-~vpI47~sV002yl1O`Ei2s;eEd=d|ZcLV?cgTVnziO4~T-9d>6M2Rc{i$o+ejZpuEz=>2OG!KQQ{r~?+i+m&y=+_AV05QNwi+m(_WJohSB`5#@01t)s1^@s^fy9Ua003KEL0myyL0&;$!w(;T00000gZTdsg`Wce07+x*iv+5J`2P=ua037UNQ)J5z9axaIo(K&LKF{#1Oos7OgZomgTMm-07#8O0ZcjY4}-G<0071UFi499M7|^dNR3bdNQ1xvOgZpKi4`)wBmfVC*aH9n#sUgRg9RbJBme>F=KTNv4<A4PNR3JXNQn(4z9;|>wn70sFAt8T0{{R>iORkK0002#dH(<Z4<A4PNR4s<NQpK5y(j<=wn70sFAt7(0{{R>iSj|X0RR91=^g$5{|_GkNR4s<NQpJoy(j<=wn70sFAt7K0{{R>iSj|X0RR91>52XS{|_GkO^N8a5C8-KOo``7Dez2*!c2)oBnaru`v3n-i$o*{NQ(_2As_&{000C4z5xIL08fo91WYNyOo{L4`1=3<Ndd)7iQ-I&Epxpn071q@002#iq$B_U1OVx={r~@F4<Cd800000Nh$TY5C8-KOo``AiRw#@94zQ*`v3n(iw(jcAON}m00aQO0RR91OeyL}iQnj*`v3n(0mDd*6%)NA07!`)6ul?_#sdINiKHX|00aO`i!B1ZC;;gh{Qv(CA4C8ENh$TY5C8-KOo``AiRw#@94zPw`v3n(iw$BRAON}m00aQO0RR91OeyL}iQniw`v3n(0mDd*6|=k~07!`)w7e()#sdINiKHX|00aO`i!GwOC;;hA{Qv(CA4C8Exex#Z05Q@`iSA5^=jg8a|Nlsf4F@0~0J;DG1OUDP0000?iRb9$`Tze+0pLuD=17SJV7w>*#sC0854Hp(O^Ku=000C4Op7f^yeI%X3J-)J`~UwuAP<BX`~UyxH~atp4<A4PNQ(`zA0Pm_000C4z5xIL08EMJ=#TmT|4aekOo`@5i3JM0C;-L)06`D71SCy~q$B_U1OQBnE%Uo506Yp0gkJmq|2!ZMgjW0i|LJl2|NmwWA4C8ENQ(_wA0Pm_000C4z5xIL08EMJ=r{TQ|4aekOo`@5i3PH|C;-L)06`D71SCy~q$B_U1OQBnEt|V206ZWMgq{2U|2zs0gq8dM|LM8=|NmwWA4C8EOgZomgW3TA01vhW5FaD}hyv;U{Qv)uNMp!Ei!6#kgZ=*xg-QVc06~exM2Re_=?(n<{|_GkNMq=W9IAu+{||*20RRAr!-*V<>EiqU{|_I400000NMp!Ei!6#kgZ=*xh2a1I06~exM2Re_>2v)5{|_GkNMq=W9IAu+{||+$0001q!-*V<=}7$l|4559;JPRP>Dl`K|4559)Ve4D={EZR|450}G41Ir`v3n(iPkaO>ACv<|3xwF=~Dau|454sEFK^LOey-l0RR91Oo{*KT=@V0O^LrqoCE+&iTdd${Qv(<iO4~T-RX+^|Nk-D>3917|1s_9+4=wfMKSH^2>bv4NQ({S9UuTqDf+$v0000?iT~&o`2YV+iN8pk1OQBl`so7v|Nl&5!$OM$f`j<~4~2^W004;`s_8%f|Nl*6#X^e&f`j<~bz($`EQ;w3|Ns9?W5Ys=1cHP3|8+Kr9IENo{{R0?W5q&?1cHP3|8)sOi7blgr2hZ^Ok?Omi!`c({{Ih!t^fc4LWu-|L5aod-biEEi!_>p{{Ih!fB*mhLWu-|iNou&Ok?Omi!`c({{MAYLWu-|L5aodiAZDEi!_>p{{M9`LWu-|iNon%|Ns9;iwzDPAOK7$`n~}G002yh|L8vV|Nl*izet<}08EMc=>Y!!|4d`fLW=~7gZTe-NQpF>iSX;ZOk>VMiv)^;`2TfDLWwl0iSX-`Ok>VMiv)^;`2Tfbi8Pvt@aby*|Nl&5&O(a>ii7z7bu&VVG^&a4={x`b|4d`hLW?w#gZ}?@OhSnSiiyVSq)cPbLW?w#gZ}?@ctVK;iiyVSqfBGaLW?w#gZ}>yg&hF^078ibiiyVSwM=8sLW?w#gZ}>yg@^zE078ibiiyVShe(TjBoIuAR3s=&iA*FQOo>D!7)XgsBnaq50{{R>i&P{?Op8<`C`^k?Bp^(SL?jqUi%cX4LWu;D>2&}9|455`BoIuAR3s=&iA*FQOo>D!7)XgsBnapQ0{{R>i&P{?Op8<`C`^k?Bp^(SL?jqUi%cX4LWu;D=}7<o|455`BoIuAR3s=&iA*FQOo>D!7)XgsBnarm0ssI=i&P{?Op8<`C`^k?Bp^(SL?jqUi%cX4LWu;D={W!Y|455`BoIi6!|3(`002md-{_w8|Nlsfd?a8<iNi>R|8xcDEcO5YNQ-<VNJxeMblm72_5c6t)#x_$|Nlsfd?XM|iBu#gOo>b+AWVrwBp67EOe6^CNCE%=NQ+b?NKA`VBq&UaOe7#oi$o+CNQ+D)2ttVjlIf%V|NmwWA4C8EQ%H?Hh_@&JNR1s48z2Da{Ph3-NQ*ta8Xy2jjTOckAOJ{>HD|Xd0O*qR|Nlsh4NJEq0J;DG1OPGiNQuwrT=f6{x&Z(L05SGRiQh<x1uM5G07!`iEVn2C=s)!T|45Cy0RRL5x<H%&05SIHEcE~XOpTKS00aO?i5=#)BmhM*$w9cy%*@OWA4C8ENsW5^Oo`S+iOGq`NQ3SHLHFRn>I01gk^#Ue!Gp;#h)w}WIsS>!b>KmR!2wBw!UREq`4A@n0CmM%NR1U08Xy2jjWtFZAOJ{>Js$x80O{KE|Nmw#4<Cd800000G3`l-(OyW2;z)z!@K97tjRndC002mh4O0XF07#8JO!WW%{}rYgAOQ3aA4C8ENR2(w86W^vNR0)_86W^iIrvD4<#ZWHiv@ZaAOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2&_86W^ijWvoHAOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(tQ86W^ig}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIVRuAOHY$FGzzu?-(Ee098nd<#Y^4i#-|{AOPrn^Z)<oNdN!;#sxVUAOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8ENQ;+9oCE+!iw*J^AOOAr0000;Df;Op^Z)-3A4C8ENQ+MhK~z;!NMqhe!Q%o*jT9M+0)zPfbq-sJ@LfS%!w(;T00000Ok?0ei!`Bw{{M9hiN=WniSS!pL0rR-NQwRExc~qENQ+enLWu;TNCDdG-)1fkAA|q^0001xQ%H&XNQ-|UNQM7&1?WEV|Nlsfdk9E{|8xyo=`ZsC{|_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=wtE!|455eBnU{0G$c%o1SpFNNQuIbi3&)A!URZz?g4f5NQ*m2h5ty215AlS2uz7X5OkGDgTxqHUFjC_|NmwWA4C8EF~CJJ!0XuP#PI+B4<A4PK~+IiRZ~cb^+<{PNQ3MMNQ;*U00aO`i=zMl1OQ1n)DMIi0RR9&54Hp(JPLFKJRo%}NsUA#0S_O500000NQr|000aOJwg^dy#7Kj{0f6}+bn1Zl3UuX3In;EwNsUA#6i7M34~BvO0075D0000007#3I000C454Hk4Ep$yW(lN<AFMkN@GY=mCi&X%P6q1AB4~+y+iA4ZNi-Q0F1OP~lPytAZlK=n&01vi60X#2%*M!M*1NU73NQ1-(TU|k1L0!WSA4C8ENR2`PNQr|000aOJwn70sFMisKRRFmG0002%rVk$gOex|_iRMU&-${wpPK_ih=u7bb|454sG!`HLx&QzK08EMJOeyNV0RR91=nwG!|49MFOo^ii00aO*#snk)NQs*O00aQ(GXMYo4<A4PNQ({m6(9h*000C4z5xIL07!}7Nr~L()bIcQNCDVLiGv6L1OUbW01vhUNQs*O00aO?i<1Zd1OPlB4}`M*|NlG+4}_}z|NrUC{{R1wL03UmNr~4%RY6otjU}EEAOKZJjV-1UAOKTAiTz25_Dm_|NQ3MMNWuLB=-2N5|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF30UHB5XaE2J3;+NCobLbsv;Y7AZ14a7+yDRoeDDAN1Ofm69QyzNSONe54Ez88ga7~l9Q^<P6afGLJpBLvECB!joc#a)WB~vG%>4iVgaH5m?EU}$$N>NVeE<LdbOHbX?EnA&yaE6K6aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|SfcpRcD*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|S;O+na&;S4c01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)i0=RY2mk;800000000008~^|S000000eVnOQUC#X5C@wD6d(W_8w>{skO2Sy6aWAKBme*a0Q>*{8vp<R1g`-A00000GynhqlmGw#2>bv4RR91007ecFi~>Op7={Bu4j_XBQwk0kLk<u^4hTpKQwk0kK@Jc?4hTXE8~^|S%m4rYF#G@iDgXcg06`8Ag92L$4hT#OK@JE2KmY&$>;M1&K>Ppy9033T06`8Ah5|tj7=r^x4ln{w3Jw@S4iG^O2u2Hd3Jw@S4iG^O2u2G6V+sx!K@Jc>4hTyNH~;_uFaZDn9Q^<Pj{yJx074EBjRHar7>ol!4j_gEK@KQ`1xgMu0<;PaC_xS&K@J!~4iG{P2u2G4Pyhe`6afGLaP9y9nhF2_1j7IT074EBj{-st7>)x;4j_#LLJla51wjrlh6X_nID-dA4!{8eP6G-KI6)3DK@KQF4j@7f7(xyZLJkN>3jhEB7ytkOzySaNy!ZeA<^TWy06`8Ag8~A}4hR4ML;wH)+yMXp0R8{}WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGBmw{cDE<Hc0ssI20000000000|Nj91|Nj9NG8O;;odF=S6ab?M{|B8E0Id`S0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005ElRd00000AQb=r00000&=vpy000000RR91000000RR91000000RR9100000zyJUM000000RR9100000-2eap000003;+NC00000hzS4y000004FCWD00000^cnyF0000082|tP00000FfAYe000008vp<R000005C8xG000008UO$Q00000KrJ8u000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000&;$Sg000001^@s600000zybgO000003IG5A00000o&f*=000003jhEB000007ytkO000006#xJL0000000000000000{{R300000ST7&|000000ssI200000AOQdX000006aWAK000002LJ#7000007XSbN00000Xb1oR000002LJ#700000Fb4nt000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000pauW{00000|NsAQ000000{{R300000@c;jB00000ZUz7V00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000NG%`$0000000000000000000000000wg~_L00000#t8rb00000)(HRr00000<_Q1*00000_6Yz0000001_}TG000007773W00000CJF!m00000HVOa$00000MhXA`00000Rtf+B00000W(oiR0000000000000000000000000000000000000000000000000000000000000000000000000002rwW3000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j9&;$Sg000000000000000000000{{mAZUz7V000000000000000000000{{pBpauW{000000000000000000000{{sCFb4nt000000000000000000000{{vDXb1oR000000000000000000000{{yEhzS4y000000000000000000000{{#Fpa}o~000000000000000000000{{&Ga0&nb000000000000000000000{{*HfC>Nr000000000000000000000{{;I^cnyF000000000000000000000{{>J02=@R000000000000000000000{{^K1RDSV000000000000000000000{{{La2o&s000000000000000000000{{~M*c|`>000000000000000000000{|2NFfAYe000000000000000000000{|5OKrJ8u000000000000000000000{|8PNG%`$000000000000000000000{|BQST7&|000000000000000000000{|ER05Bi`000000000000000000000{|HSATS^R000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000002><{90ssyGAQb=r00000<^TWy000008~^|S0RR~Qu*@g`000000RR9100000D*ylh1OV~>00000000000000000000HUIzs0ssyGKo$T1000000000000000H~;_u0ssyGfEEA%000000000000000O8@`>0ssyG&=vpy000000000000000VE_OC0RR~QI4~dp000000RR9100000Z~y=R0RR;MKrJ8u000000000000000mjD0&0ssyG5ElRd000000000000000qW}N^0RR*LFfAYe000000000000000D*ylh1OV~>00000000000000000000!T<mO0RR#J)Exi-000000000000000000001OV~>00000000000000000000&;S4c000pH1RDSV000000000000000;{X5v0RR>NNG%`$000000000000000>;M1&000yKKrJ8u000000000000000{Qv*}000yKFfAYe0000000000000005CH%H0RR^OST7&|000000000000000CIJ8d5dawgATS^R000002mk;800000IspIxA^;8mpceoD00000DgXcg00000OaTA@5C9ke7%(6J000000000000000x&i<IAOIKu05Bi`000000000000000Qvm<~5daVX02=@R000001ONa400000VgUdE5&!@I00000000000000000000hyefqA^-pY00000000000000000000qyYc`5&#YWfC>Nr00000nhF2_00000sQ~~05&!@I00000000000000000000y#W9K5ds(h2rwW3000000000000000$^ifXA^;8mAQu1t000008vp<R00000;Q;^uAp#fx5HKJB000002mk;800000w*vqG5&#bX^cnyF000000000000000{Q&>~5dawgFfbqh000002mk;8000005CQ-I5&!@I00000000000000000000D*^xj5&!@I00000000000000000000MFIc-5&!@I00000000000000000000z5)OM5&#YW5EcLc00000D*ylh00000Spon65&!@I00000000000000000000YytoP5&!@I0000000000000000000069WJM5&#PThzS4y000000000000000hynlr5ds(h7%(6J000000000000000lmY+%A^;8m@E8C900000j{yJx00000xB>tG5C9ke05Bi`000000000000000_y7O^5C9nfxXdU3000000000000000#R32T5&!@I00000000000000000000*a83m5C9nf7%(6J000000000000000<N^Qy5&!@I000000000000000000002?GEC5&#YWfEoY*00000WdHyG0000083O<S5&!@I00000000000000000000E&~7n5&!@I00000000000000000000PXhn|AOHXW00000000000000000000YXblP5&!@I00000000000000000000g988nA^;8m&=&vz000009033T00000tpfl65&#YW@EQOB000000ssI200000y#oLM5&!@I00000000000000000000+yejrA^;8mpceoD00000DgXcg00000?gIb-AOHXW00000000000000000000{R0315dawgKrkQx00000P@Dt+000000t5g6A^;8mKo<Z200000RR910000007X$zRAOHXW00000000000000000000F$4er5&!@I00000000000000000000MFao<A^;8mAQu1t000008vp<R000007ytkO5dawgpv)uy000005C8-K00000Tm%3B5&!@I000000000000000000000BvDuZZ2bE0AEK;PeMUVUte=|VqZyLW@&B!Us_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|)MLUjTD-WN&qJKtM-KNkT(kGA=SMH2_~)PB~R>X>V>uX>MdhGDUU(Uu9%rbYTErNl#yMbYy96Uv+b3WB^}UQ*<#mUte@+a&LEEVqs)oVQg$~V|GA5M@&gVLs(c}GcGg$UteQ*VP9rxZeeU`dSyUBM@&gVLtip3GA=a$ZDDC{0BvP$b7gcuKu1hTLPK9NE;24P0AF8Zb8la0VQyq>WdL7VPBunib96~hH&AkEZggdGL^4Ho07O?Va%E;NUtec<cwca3a&vEPVQgu1d0%!g0CRL?X>LG3M@&gVLtip3GA=a$UteuyZEbIMWnW`xYd}CpOi4mRUotK;E;ImNUt@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_H!MqzVwNl!OZV_|M?WpXrfWnpAVX-sJ_MMXt+QdD06UteTlbYWj}bYXII0A_M!VPrr+M@&gVLtip3GA=a$UteN#b6<0GVRCc;Us_I6bU0~mb6;X%b7eG1ZfSHwF-3MjKu1hTLPJ<sUo$Q=0AF8hX<}nvV{>(1X>MtB0BvP$ZEtpEKtM-KNkT(kGA=SMH2_~<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|0AF8hX<}nvb97;HbYE>@X>LG3M@&gVLtip3GA=a$Us_H%Rc>i-ZboTtWJEDVb^u>rXKin8UvqR}a&%u`0A_D>bO2vkPB~R>X>V>uX>MdRa&K>RMQH$ENmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0A_b`X>?^kKu1hTLPK9NE;24P0AE^8Hb!A{bV*M)P;zN*bY*fxF-3L&Us_I6bU0~mb6;X%b7eG1ZfSHxF-3MjKu1hTLPJ<sUo$Q=001s?d2MuIVgN34baHfIVgN34XmfOObYWruE@^IbWpZ!;E^cphWiCNNNiB3?X8<m4Z**lYXKr;aVs&Y3WG!iA04`^4buMUOb7%lAWO;6Ld2IkLWO;6LbaDVLXKr;ac4cyNX>V=-E@y6aE_P*db7^mGUvdC0a%F5`E@XLb04{Q6Y+){NY;*uFX>MtB04{KBbS`IabO0`NWq5P|E@o+NX#g&AZ)9O~VE`^=XkTV>VQpn!Xk>B#E@fz6W^!R|WdJT`V`E=scw=R7bYFB~Vr*pqE@^IQbYEd|a$$J@E@o+NX<uP-a$$J@E@XLbVQpz+04`)<bYTE4Vsmo<E@N+PZDnqB0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO000005CQ-I000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000&;$Sg00000&;$Sg00000o&f*=0000000000000000RR91000000000000000UH||9|NsAQ0ssI200000ZUz7V00000ZUz7V00000EC2ui000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000pauW{00000pauW{00000kN^Mx000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000Fb4nt00000Fb4nt00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000Xb1oR00000Xb1oR00000AOQdX000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000hzS4y00000hzS4y000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000pa}o~00000pa}o~00000&;S4c0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000a0&nb00000a0&nb000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000fC>Nr00000fC>Nr00000au5Ij0000000000000005C8xG000000000000000qW}N^0RR911^@s600000^cnyF00000^cnyF000002><{90000000000000001ONa4000000000000000sQ>@~0RR915&!@I0000002=@R0000002=@R000001ONa40000000000000001ONa4000001ONa400000u>b%70RR910ssI2000001RDSV000001RDSV00000YybcN0000000000000001ONa4000000000000000zW@LL0RR910ssI200000a2o&s00000a2o&s00000XaWEL0000000000000002mk;8000000000000000$p8QV0RR910ssI200000*c|`>00000*c|`>000009smFU0000000000000000RR91000000000000000+W-In4gdfE0{{R300000FfAYe00000Ff9N8000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000KrJ8u00000KrH|O000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000NG%`$00000NG$*W000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000ST7&|00000ST6to00000r~m)}0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000005Bi`0000005AXm000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000ATS^R000007%%_;00000n4Aaz000000000000000AOHXW0000000000000002LS*80RR91FaQ7m0000000000000007%%_;00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NH72Z00000hzI}x000008~^|SE&u=k2mk;8000007ytkO000002><{90{{R300000000000000000000&^Q1900000fdl{m0000000000000000RR910000000000000005dZ)H0{{R300000000000000000000Q9S?v000005CH%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:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()

from libc.stdio cimport scanf, printf
cdef int i
cdef int N, Q
cdef int t, u, v
scanf("%d%d", &N, &Q)
cdef dsu *d = new dsu(N)
for i in range(Q):
    scanf("%d%d%d", &t, &u, &v)
    if t == 0:
        d.merge(u, v)
    else:
        printf("%d\n", d.same(u, v))
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
import sys
from random import *
from collections import *
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        # self.size_table = [1] * n
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        # self.cnt -= 1
        # self.size_table[ru] += self.size_table[rv]
        return

    # グループの要素数
    # def size(self, u):
    #     return self.size_table[self.root(u)]

n,q=MI()
uf=UnionFind(n+1)
for _ in range(q):
    t,u,v=MI()
    if t:print((uf.root(u)==uf.root(v))*1)
    else:uf.merge(u,v)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[i for i in range(n+1)] #自分が親なら自身の番号を、そうでないなら（元）親の番号を示す
def r(x):   #親は誰？
    if root[x]==x:
        return x
    else:
        root[x]=r(root[x])
        return root[x]
def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    root[y]=x
for i in range(q):
    t,x,y=map(int,input().split())
    if t==0:
        unite(x,y)
    else:
        if r(x)==r(y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
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 [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Union-Find -- START --
class UnionFind():
  def __init__(self,sz):
    self.sz=sz
    self.data=[-1]*sz

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

  def find(self,k):
    if self.data[k]<0:
      return k
    self.data[k]=self.find(self.data[k])
    return self.data[k]

  def size(self,k):
    return -self.data[self.find(k)]
# Union-Find --- END ---

def main():
  n,q=LI()
  uf=UnionFind(n)
  ans=[]
  for _ in range(q):
    a,b,c=LS()
    b=int(b)
    c=int(c)
    if a=='0':
      uf.unite(b,c)
    else:
      ans.append(1 if uf.find(b)==uf.find(c) else 0)

  for x in ans:
    print(x)

main()
# print(main())

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
uf = UnionFindTree(n)
for i in range(q):
    t,u,v = map(int, input().split())
    if t==0:
        uf.connect(u,v)
    else:
        if uf.root(u)==uf.root(v):
            print(1)
        else:
            print(0)