Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

Solution code:
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91&=3Fs00000KmY&$00000C@ug10000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000<rM$`00000<rM$`00000001BW000000RR911^@s6FdYB@00000FdZNO00000FdZNO00000=mG!$00000Pz3-000000001BW000000ssI21^@s6NF4wG00000NF5*m00000NF5*m000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4z!Lxf00000z!Lxf00000z!Lxf00000OaK4?00000OaK4?000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4FdYB@00000FdZNO00000FdZNO00000&;kGe00000&;kGe000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$659RjAE5T+sfL%29NplK0#+DD0ssI26aWAK0RR911^@s6000mI0RRL56aWAK000006qpP{bCw4J000000000000000000000000000000#sB~S5&!@I00000000000000000000<^TWy5&!@I00000000000000000000m;nF)A^-pY00000000000000000000Y5)KL5&!@I00000000000000000000RR9105&!@I00000000000000000000eE|Rf5&!@I00000000000000000000iva)t5&!@I00000000000000000000-v9sr5&!@I000000000000000000009RUCU5&!@I00000000000000000000YykiO5&!@I00000000000000000000BLM&a5&!@I000000000000000000002mt^95&!@I00000000000000000000U;qFB5&!@I000000000000000000009{>OVAOHXW00000000000000000000Qvm<~5&!@I00000000000000000000rvU%}5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000t^fc45&!@I00000000000000000000I{^Ry5dawgKp-Fh000005CH%H00000r2qf`5dawgU?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)zN@MN(-1Us_I6Z)|f#X#ihZQ*<<CZe(mpV^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9k0AE^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^ecWnS)T251RIB9QlUt(c%Wi&}{X>>y|MRovRT2pj1V{dhI0BmVuXJcbub1rjlE-?UKRc?1_Ze(9lWpj0HWdLkxVq-3IZ!R_fUte={VPk7wV`yt%W?^Y;0AF8Wb8}^KbYEs+X>0&rUt@S-Utx4*cxiM1UteQ*VP9rxZeeU`dSw7#Uu<b&V_$Q0VRCd|ZDDC{07pYZUo$Q+07pzoLPK9NE;Il~Oi4mRUotK-E;Rr{SXe<qNnbH8GXO_SNkT(dSYI<PGynhq0ssO40{{X50ssR50{{X50ssU60ssX70ssI21^@#9000000ssO40ssI2000000RRC2MF9W+5C8xGAOHXWP$qc`000I6xd8wG000000RRF3VgUdE5C8xGFaQ7m6lrM<000C4!2tjO5C8xGbsA|200093%K-oY000000RRF30RR915C8xG00000)30j<000F5*8u<k5C8xGbSaVu00062;sF2v00000FdZNO000002mk;800000&=CLt00000I2|AW000002mk;800000pb!8600000Kph|e000002mk;800000kP!d?000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s60{{R30000000000*dHJO000001^@s64gdfE0000000000;2$6W000001^@s65C8xG0000000000=pP^e000001^@s65dZ)H0000000000@E;%m000001^@s65&!@I0000000000_#Yqu000001^@s66951J00000000005Fj7`000000RR913;+NC0000000000Kp-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#74FCWD0000000000$R8j8000002LJ#74*&oF0000000000NQ3MMNQ(s(79apfg}`(I|IkQ-#0bLx|229QAOQa*d=(%74<A4P|0Q}AAOL6p0002#;Q#;s|0Qx2AOL6q0002#(EtDc|0QY_AOL6r0002#!2kdM|0QA-AOL6s0002#u>b%6|0P-#AOL6t0002#p#T5>|0PltAOL6u0002#kpKVx|0PNlAOL6v0002#fdBvh|0O~dAOL6w0002#aR2}R|0OyVAOL6x0002#VE_OB|0OaNAOL6y0002#Q2+n`|0OCFAOL6z0002#K>z>$|0N<7AOL6!0002#F#rGm|0Nm~AOL2N0000000000L03UmG5<kTK~z;!NQ3NnWJrqyB`5#@07!{MBxo_f=o|n4|45B=Brr&gJ#Q8u07%CLOcx*k00000=pX<8|45B=Bs55g$LJFO|Nls1TqH0^$3!GZ00000NXJAZPyhe`07%C~Bv=3d002mZ+lgExKo5mm0RRAtL?kqYzz>cK0{{Rq?M#hiBsffsEejSP08EW^Bs@%wd?Y~YU=JUF00000NMp)K!Qlc-jRX%tivWed4~hB!0024DbTUX|!$^%Zhe%_>NR14KM2iNC0YN#yeiMnuM2WzO(?N;&NQuu#iSbB@{zL)5i3W)ogT(<kY$P-fjz0ka08EMIOo{L4RQ~_}Oo{eLiO1+k{{R1rL?k$kSpSPeBs_)NiCiQ&jZpuIR3tnPh!z6?0E=`aK#9=z(81^*Ir9&k!GysNg#H2m06FpxjrIZn07#2`BuGeO%SgfD0!)nz4?&9og}@JpIRF3uImUh<Ok==8iyViA+YgDr0RRAr!$FA|i*zJFIr0yT6#xJKNR1682LJ#_jWwbM002mhJ*fr&0J<Xp008K{{r~?DA4C8EIq-ehNMq1Miwu`Vg~<<zPXPb`L5To~!s+P#|Nlt1|NsC0|Ns9#NIAm~hwlRb07#82od5s;07!}N=%@Yv|45AtC^6EI#{`i7|Ns9;gTetwIn#CUNQ-<VNJxoHBv43+L?lQ^iA*F|NQM7&1?Xb^|Nn!0Bs2gIk52yo{|_I400000i&P{qh0+g>Mgaf-i&P{)h0+g>aRLAUNQ-<VNHN<n?M#hqBtYvZ4<Cd800000_t-hb4@~HdLjgHNBrtwai&P{)NQ1)xIl>Q)IRXFxOpPR+00000N{tLBivfkec+NS{4~^>n|Nl&5@Jfv|w?vBuMTNi*iKYMm0Eq#M2KU%G#ScvAjY9!BL?keOuSktOs1hImiSFp}{Qv(*iO1+^{Qv(*i+m(VNQM7&1?Zam|Nk+-NQ-nNXk<t;G$kki000k#s{#N3NQ1<9TU|k1L0v&!L0`i`Iq?sTaQ^@QO=H1Aiv)*-zz>On0000)i42!ajRX%wiOA`R{{R0u-VcsR{{R0>W6MH|1doNlc|$^p9EVJe3=iod{{R0$InWP{DE|NdNn^l^42MjOJcR%N004!_c~?k{G>1ls1h-0!3@1d1!09Xh|Nk-V={W!Y|2f7Fj`RKh|43ulM2j4sMTOgWWI~AqkBP(Up*ipmjo1DE|4d`ZMvEMeMTOgWD?*6`he3(K>0bZ;|2feQjko>(|4d`SLW?wqh4y(#NMpf5i3~qUiNNcML^<9Mj+g!a|4n1lLW=~Kg}`}YMu{AcM2XnzxI{VL4~}~M|Nl*6(?W{`mxaK2VMK`>pG1k+>3skH|2ftVja&Wy|43ubiv*8_z<Fjui8P0a@#~#PjSY?j002mhHR}Ta07#8J2m}BCx-b9$0O$t$|NlA04~`=J|Nl&5*g}gmpM~~$YeI<xmqCfc>w-DP4~_=?|Nl&5*g}gmpM~}hiJJfb078ibmqCfc>3skH|2fbPjpO|P|43udi!_&o_79220001q1doZv>3aYF|45Au&;tMfNR2gZ0{{R>jXiV&006o>0002!i2DEkOo{(YiCiQoOo>z^AWVr&Bp6JIL?jSMiBu#ANQn$2=o10}07#2`BuGq)TqGz=i&P{aOp8n;7)*;qBoIi8R3r#Oi3FcWiwq>`MgRZ*Oo{(YiCiQoOo>z^AWVr&Bp6JIL?jSMiA*F2i4-L0!~p;RNQ-<VNKA`dBq&UaR3sowi%cXKOp8P$5J-zmBnU!@1fPo(B<UCb|Nl&h??{PMBoIi6Oe6?Qi3B9*gaH5mNQ-<VNJxuRBoIi8Oe6?Qiv%Qz1efUu|NsB!^!fk)NQ-<VNJxppNQM7&1?a;0|Nlsd-{=bZ|Nrac=u`Rs{|_GkNR2(x5g-6agX{?C(E0!WNQ*r|4<G<YjTK4{AOJ{>HM9{R07!$x2<dY9|Nmx?G3`l-(OyW2;z)z!@K97tjRpDv002mh4TAvy07#8J%=!QS{}tvAAOQ3aA4C8ENR2%a4<G<lNR0&v4<G<YIrvD4<#ZWHiv_w4AOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2(w4j=$XjWx;+AOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(u54j=$Xg}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIZ<5AOHY$FGzzuFAg98098nd<#Y^4i#=KnAOPt7`2YXtNdN!;#s#?$AOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8Eh4w*IRa1CfNQwQ6KRNe)R7i_W2uNezNWtR*NR1R3ivoqfc?w&J@LfS%!w(+-Imdo6Ok?0ei!`By_IVMB#)$%n@LOF$T*GD$A4C8ENQv+0sQ>@}NQ+enLWu;TNCDdG+DMHJGywnrNR2hI0000;jXk&k006op0002!%=iEQW-bpOga7~l003r?L03UmNr~4%RY6otjU}!MAOKZJjV-ncAOKTAiTz25_Dm_|NQ3MMNWuLB=qLC8|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP000000000000000000000RRF3L|;a7X=QF?b1q|WZ~!nMJUt+IASNatcpy9=ZeIWZ00000Fd#fVAb21qCLnkqJRojgASNatFd#fVAbB7rCLnnrJRojg0000000000000000000000000X>N2NRc>i-ZboTtWI8%?X?kTSX>N2W0000000000X>N2NRc>i-ZboTtWI8%>Z*O!cX>N2W0000000000c5i89AXRQ@Z*E3uZe%(-b#7^NWhiNGbSxlgZgeRC0UHB5OaK4?2mk;8Aol<Nm;e9(@b>@zzyJUM0Qdj@FaZDn;QaspgaH5m5dHuEXaE2JApZaV*Z=?ku>Sx5paB2?ApigW=m7u#000006aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|Sp#1;;D*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|Sfc5|X&;S4c01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)DE9yV2mk;80000000000GynhqTmS$7K>h#!ga7~l07MQDi~>Op7={Bu4j_XBVG0fyLk<u^4hTdGRtgRnK@Jc?4hTmJ8~^|S000000eVnOQUC#X5C@wr3m^a+8w>{skO2SyPyhe`Bme*a$o2pK-30&u1it_P074EBj{-st7>)x(4j_#LLJla51wjrlh6X_nID-d74zK|O00RmRI6)3DK@KQF4j@7f7(xyZLJkN)3jhEB7ytkO2mt^9RQvz`E&u=k080)KUJeKV00000L;wH)Bmn>b2>t*6WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGYykiOF#Z4k0ssI20000000000|Nj9YAT9s^hXN413jp*31=b4y+64`~3jomz1polp3kB8-0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000&=CLt00000pb!8600000kP!d?000000RR91000000RR91000000RR9100000MF9W+000000RR9100000VgUdE000003;+NC00000$O!-d000004FCWD00000<Prb?0000082|tP00000FdZNO000008vp<R000005C8xG000008UO$Q00000Kph|e000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000&;$Sg000001^@s600000zybgO000003IG5A00000?g0P*000003jhEB000007ytkO000006#xJL0000000000000000{{R300000SRWt&000000ssI200000AOQdX000006aWAK000002LJ#7000007XSbN00000s0aW6000002LJ#700000a0dVY000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000@CE<?00000|NsAQ000000{{R300000@c;jB00000z6JmQ00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000NF5*m0000000000000000000000000_6Yz0000001_}TG000007773W00000CJF!m00000HVOa$00000MhXA`00000Rtf+B00000W(oiR00000b_xIh00000h6(@x00000mI?p>00000rV0Q60000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j9&;$Sg000000000000000000000{{mAz6JmQ000000000000000000000{{pB@CE<?000000000000000000000{{sCa0dVY000000000000000000000{{vDs0aW6000000000000000000000{{yE$O!-d000000000000000000000{{#F;0XW#000000000000000000000{{&GunGVG000000000000000000000{{*HzzP5W000000000000000000000{{;I<Prb?000000000000000000000{{>J022TJ000000000000000000000{{^Kz!Lxf000000000000000000000{{{L5EK9a000000000000000000000{{~Mz!d-h000000000000000000000{|2NFdZNO000000000000000000000{|5OKph|e000000000000000000000{|8PNF5*m000000000000000000000{|BQSRWt&000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000004*&oF0RRvHfD-@!0000082|tP00000I{*Lx0RRvHpc4Q900000AOHXW00000X#fBK0RRvHU=siU0000082|tP00000l>h($0ssyGpb!8600000E&u=k00000sQ>@~0RR~Qc_JVH000000RR9100000xBvhE1OV~>00000000000000000000!vFvP0ssyG01*HH000000000000000#Q*>R0ssyGKoI}{000000000000000*Z=?k0ssyGkP!d?000000000000000?f?J)0RR~Qcp@MG000000RR9100000{Qv*}0RR;MKph|e000000000000000Bmn>b0ssyG&=CLt000000000000000FaZDn0RR*LFdZNO000000000000000xBvhE1OV~>00000000000000000000PXPb`0RR#JycGZd000000000000000000001OV~>00000000000000000000T>$_9000pHz!Lxf000000000000000Z~*`S0RR>NNF5*m000000000000000c>w?b000yKKph|e000000000000000iU9xs000yKFdZNO000000000000000odEy<0RR^OSRWt&000000000000000vjG4A5C9ke7$6`3000000000000000U;_XEAOIKu03aX$000000000000000x&Z(H5daVX022TJ000001ONa400000$pHWW5&!@I00000000000000000000?*RY+5&!@I000000000000000000009s&RWA^-pY00000000000000000000qyPW_5&#YWzzP5W00000-30&u00000IsyOy5&!@I00000000000000000000f&u^l5ds(h2p}K;000000000000000j{*Py5&!@I00000000000000000000rvd-~5&!@I00000000000000000000!U6yQAp#fx5Fj7`000002mk;800000A_M>c5&#bX<Prb?000000000000000-U0vs5&!@I00000000000000000000_yPa`5&!@I00000000000000000000WCH*I5&#YW&=3Fs00000D*ylh000003<CfF5&!@I000000000000000000009|HgY5&!@I00000000000000000000rUL)~5&#PT$O!-d000000000000000I|Bd!5ds(h7$6`3000000000000000M*{!=5dawgKp-Fh000005CH%H00000UIPFC5C9ke03aX$000000000000000g#iEn5C9nffFd9O000000000000000YXblP5C9nf7$6`3000000000000000cLM+b5&!@I00000000000000000000oC5#=5&#YWa1sCj00000WdHyG00000tOEc55&!@I00000000000000000000%>w`c5&!@I00000000000000000000<O2WzAOHXW0000000000000000000000aO45&!@I000000000000000000007z6+S5&#YW;1U1;000000ssI200000C<Fii5dawgU?Cs?000007y$qP00000J_G;&5&!@I00000000000000000000T?7CCAOHXW00000000000000000000Yy<!RA^;8m;1K`-00000ga7~l00000fdl{mAOHXW00000000000000000000n*;y=5&!@I0000000000000000000007PF#a%p95WOFWKaBu)$T3SvyRc>i-ZboTtWHfSbZ*)azMKL*FUr<s-R8(1CMpaHjR7p=xUta)UT3SvyRc>i-ZboTtWHoheX>?^pX=z0<IbUB;Qbkl$Szks~PD4~lPflN70AE^KPB~R>X>V>uX>MdRb7^{IMQKGbIbUB;Qbkl$Szks~PD4~lPflN70AEK;PeMUVUte=|VqZyLZDDC{0AE^DbWAv3Uukb?ZfSG?V{&wJbaiHCE@J>>WpZU_X>)XCa$j_9Ut?@<Ze?=-UteTzUuSG@Vqt7wWOQ$Gb6;U~cmQK>ZE$R5bY)~NH#Rvq0AF8ZZ(nC@Z(?C=Uu1M|a&uo{b$DN9X>Ms>VRCX|d0%C2baHtBW^!R|WnW}<ZEbk~UteZ&VQpn!WOZ$Ad0%O6X>?y<a&lpLUuAA|a(Mt>Uq(_vO+{ZtPDEc{0AF86PE}t;NMA-$K}|(pNJLTqUqo3>K}|_R0AF8eZfSI1VRCX|d0%C2WB^}ZX>MtBUtw}`VR>J3bYXII0AEK;PeMUVUr$CxQ$<u?R6#;aMPC44Wn^J=VE|uAPhWF%WNB_+b#rB80AE^DbTKzyUvy}4Z+Bl}VPs!nY;131c0fQ!Oi4mRSXf^(E;ImNT251RIB9QlUt(c%Wid5#d2VB0cWHEJUvqS1X>UbhKtM-KNkT(dSYI<PGyq>;V|Za-W@&C=Y-xIBKtM-KNkT(kGA=SMH2_~)Q*<<CZe(mpV^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9kKtM-KNkT(dSYI<PGyq>;WOHv{Xkl(-Y-IpnT251Ga&tveX+S_nOi4mRSXf^(E;ImNUtx1|WpZ?1W?^Y;KtM-KNkT(kGA=SMH2_3cE^=jNE?-|~cz9oMWpZ<GZeeU`ba`KPFaTd)V|Za-VRU79X>>q9M@&gVLtip3GA=a$Us_~rP<B8-M@&gVLs(c}GcGg$Us`T=Z9qUrOi4mRSXf^(E;ImNUvqR}V{2byXlq|)VQFkYKu1hTLPK9NE;ImNUsO#)UqwztUta)UT2pj1V{dhIKtM-KNkT(dSYI<PGyq>;WMOn+UvqR}a&!P+Ut)7}UvqR}a&!P+T251RIB9QlUt(c%Wi&}{X>>y|MRq_yM@&gVLs(c}GcGg$Uter#Vq;%pb9G;7ZfSG?Utec<cwca3a&vEPVQgu1d0%!gKtMxSSV2NbUokE-0AE^8Q*Uf@MQK1lM@&gVLs(c}GcGg$UrAI=Uu0!+WoKz~bY*f>O+##NZe>(qVr*pqUsY~*X>Md+Qe|^>ZDl|}M?*tjGcGUyUter#Vq;%pb9G;4X>Mr%Us_XiGh=CPKtM-KNkT(dSYI<PGyq>;Y-wU+UvqR}a&%v9VQFqaKu1hTLPK9NE;24P0AF8cZEtR0b97;HbYEWpUs_H%Rc>i-ZboTtWHfSbZ*)az0AEQ|O<!_lXK8bEWpY$aLu_wuWmI8eY-IpnT251RIB9QlUt(c%Wi&}{X>>#}MRq_yM@&gVLs(c}GcGg$04{TRZFFH`04{TMa&%#004{TAb98caVPXI-X>N37a&Q1HZf|sDE<r*`Ep%aL04{ECbY(7QZgnnVb!lv5Eoo!`E@y6aE@)wMXaFu`d2VxgZ2&H0d2VxbasV!8ZgnnpWpZ<AZ*BlCXKr;ac4cyNX>V>{asV!JWo%(CWO;4?E^=jTVJ>iNbO0`CZfSG?E^usgE@y9a04{W8cys_RW@&C|04{QGWMOn+04`-{UuJS)ZDn6*WO4v5WoTb!a$#*{04`@^V_#)>V`Xr3Uvyz&Y-Ip0X>MtBUtw}`VR-;9W@&C|Utw}`VR-;9WO;63ZE0fwE@WYJVE`^-b8`SLV{dJ3Wo~o;000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO000005CQ-I000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000&;$Sg00000&;$Sg00000?g0P*0000000000000000RR91000000000000000UH||9|NsAQ0ssI200000z6JmQ00000z6JmQ00000EC2ui000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000@CE<?00000@CE<?00000fB*mh000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000a0dVY00000a0dVY00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000s0aW600000s0aW600000AOQdX000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000$O!-d00000$O!-d000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000;0XW#00000;0XW#00000&;S4c0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000unGVG00000unGVG000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000zzP5W00000zzP5W00000A_xEg0000000000000005C8xG000000000000000qW}N^0RR911^@s600000<Prb?00000<Prb?000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000022TJ00000022TJ00000zyJUM000000000000000AOHXW000000000000000u>b%70RR910ssI200000z!Lxf00000z!Lxf00000OaK4?0000000000000001ONa4000000000000000zW@LL0RR910ssI2000005EK9a000005EK9a00000umJ!70000000000000002mk;8000000000000000$p8QV0RR910ssI200000z!d-h00000z!d-h00000B>(^b0000000000000000RR91000000000000000+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?J000005C{MO000008~^|SF#rGn2mk;8000007ytkO000002><{90{{R300000000000000000000SSSDh00000zytsQ0000000000000000RR910000000000000005dZ)H0{{R3000000000000000000007%cz*000005CH%H0000000000000000RR91000000000000000"

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.rank = [-1 for _ in range(n)]  # 根の深さ

    # xの属する木の根を求める
    def find(self, x):
        if self.rank[x] < 0:
            return x
        else:
            self.rank[x] = self.find(self.rank[x])
            return self.rank[x]

    # xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] <= self.rank[y]:
            self.rank[x] += self.rank[y]
            self.rank[y] = x
        else:
            self.rank[y] += self.rank[x]
            self.rank[x] = y

    # xとyが同じ集合に属するかを判定
    def size(self, x):
        return -self.rank[self.find(x)]


N, M = MI()

if M == 0:
    print(1)
    exit()

uf = UnionFind(N)
for _ in range(M):
    a, b = MI()
    a -= 1
    b -= 1
    uf.unite(a, b)

ans = 0
for i in range(N):
    ans = max(ans, uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
# Union-Find
a=list(range(n))
def find(x):
  g = x
  while g != a[g]: g = a[g]
  a[x] = g
  return g

for _ in range(m):
  x,y=map(int,input().split())
  x,y=find(x-1),find(y-1)
  if x == y: continue
  a[y]=x

count=[0]*n
for i in range(n):
  count[find(i)] += 1
print(max(count))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、要素の個数を負の値で保持している
            return x  # 自身が親であるということ
        else:
            self.parents[x] = self.find(self.parents[x])  # 再帰的に親を探しにいく
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)  # この変数xに格納されているものは必ず根のノード
        y = self.find(y)  # この変数yに格納されているものは必ず根のノード
        if x == y:
            return  # もし同じ親ならば何も起こらない

        if self.parents[x] > self.parents[y]:  # それぞれ、要素の個数が負で格納されている
            # yのグループの方が要素が多いの場合（yの方が値が小さいということは、負の世界では値が大きいため）
            x, y = y, x  # 必ずxの方が要素が多い状態にする

        self.parents[x] += self.parents[y]  # 負の値だが、これでいい
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    def size(self, x):
        return -self.parents[self.find(x)]  # 親まで辿ればグループの大きさが負で格納されているため、それにマイナスをつけてreturnする

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 親が同じならTrueが返却される

    def members(self, x):  # この実装変じゃね？
        root = self.find(x)  # 親の値を取得する
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        return len(self.roots())  # グループの数を返す

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}  # 親のノード番号をキーにして、子のノードを対応させた辞書を返す

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    uf.union(a, b)

ans = 0
for a in uf.roots():
    ans = max(ans, uf.size(a))
print(ans)

Submission status: Accepted

Solution code:
import sys


def _ia(): return map(int, sys.stdin.readline().strip().split())


class UnionFind:
    def __init__(self, n):
        self._par = [-1]*n

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self._par[x] > self._par[y]:
            x, y = y, x
        self._par[x] += self._par[y]
        self._par[y] = x

    def size(self, x):
        return -self._par[self.root(x)]


def main():
    n, m = _ia()
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: x-1, _ia())
        uf.unite(a, b)
    return max(uf.size(i) for i in range(n))


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
abm = [list(map(int, input().split())) for _ in range(m)]
abm = set(tuple(sorted(item)) for item in abm)
edges = {}
for a, b in abm:
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    if b not in edges:
        edges[b] = [a]
    else:
        edges[b].append(a)

import collections
vis = [False for _ in range(n + 1)]
gr = {}
def create_group(s):
    if vis[s]:
        return None
    
    deq = collections.deque()
    deq.append(s)
    group = []
    while len(deq):
        node = deq.popleft()
        if vis[node]:
            continue
        group.append(node)
        vis[node] = True
        for e in edges.get(node, []):
            deq.append(e)

    for g in group:
        gr[g] = s
    return group


groups = [create_group(i) for i in range(1, n + 1)]
groups = list(filter(lambda x:x, groups))

ans = max(map(len, groups))
print(ans)

Submission status: Accepted

Solution code:
import sys

def _ia(): return map(int, sys.stdin.readline().strip().split())


class UnionFind:
    def __init__(self, n):
        self._par = [-1]*(n+1)

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self._par[x] > self._par[y]:
            x, y = y, x
        self._par[x] += self._par[y]
        self._par[y] = x

    def size(self, x):
        return -self._par[self.root(x)]


def main():
    n, m = _ia()
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: x-1, _ia())
        uf.unite(a, b)
    return max(uf.size(i) for i in range(n))


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

seen = [None]*N
ans = -1

for i in range(N):
    if seen[i]:
        continue
    seen[i] = True
    tmp = 0
    d = deque()
    d.append(i)
    while d:
        v = d.popleft()
        for i in graph[v]:
            if seen[i]:
                continue
            seen[i] = True
            d.append(i)
            tmp += 1
    ans = max(ans,tmp)
print(ans+1)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parent = [-1] * N

    def root(self, A):
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        A = self.root(A)
        B = self.root(B)

        if (A == B):
            return False

        if (self.size(A) < self.size(B)):
            A, B = B, A

        self.parent[A] += self.parent[B]
        self.parent[B] = A

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


N, M = map(int, input().split())
uf = UnionFind(N)

for i in range(M):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(N):
  ans = max(ans, uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

par = [i for i in range(N)]

def find(x):
  if par[x] == x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]
    

def unite(x, y):
  x = find(x)
  y = find(y)
  if x > y:
    par[x] = y
    find(x)
  else:
    par[y] = x
    find(y)
if M > 0:  
  for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
  
  ans = [0] * N
  Max = 0
  for i in range(N):
    find(i)
  for i in par:
    ans[i] += 1
  for i in ans:
    if i > Max:
      Max = i
  
  print(Max)
else:
  print(1)

Submission status: Accepted

Solution code:
class DisjoinSet:
    def __init__(self, N):
        self.par = [-1] * N
        self.sz = [1] * N

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

    def unite(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        if self.sz[a] > self.sz[b]:
            a, b = b, a
        self.par[a] = b
        self.sz[b] += self.sz[a]

    def same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, x):
        return self.sz[self.root(x)]

    def __str__(self):
        clusters = defaultdict(list)
        for x in range(N):
            clusters[self.root(x)].append(x)
        return str(list(clusters.values()))


N, M = map(int, input().split())
dsu = DisjoinSet(N)
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    dsu.unite(x, y)

ans = max([dsu.size(x) for x in range(N)])
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
tree = [0]+[i+1 for i in range(n)]
size = [0] + [1 for i in range(n)]
def find(c):
    pc = tree[c]
    if pc == c:
        return pc
    else:
        return find(pc)

for _ in range(m):
    a, b = map(int, input().split())
    pa, pb = find(a), find(b)
    if pa!=pb:
        if size[pa] < size[pb]:
            tree[pa] = pb
            size[pa], size[pb] = size[pa]+size[pb], size[pa]+size[pb]
        else:
            tree[pb] = pa
            size[pa], size[pb] = size[pa]+size[pb], size[pa]+size[pb]
            
print(max(size))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    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
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
      
uf = UnionFind(n)
for i in range(m):
  a,b = map(int,input().split())  
  uf.union(a-1,b-1)
  
ans = 0  
for i in range(n):
  ans = max(ans,-uf.parents[uf.find(i)])
  
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
n,m = map(int,input().split())

d = defaultdict(list)

if m==0:
    print(1)
    exit()

visited = [-1] + [False]*n
for i in range(m):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
maxi = 1
for i in range(1,n+1):
    if visited[i]:
        continue
    cnt = 0
    que = deque([i])
    while que:
        v = que.pop()
        if not visited[v]:
            visited[v] = True
            cnt += 1
        for j in d[v]:
            if not visited[j]:
                que.append(j)
    maxi = max(maxi,cnt)
print(maxi)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n: int) -> None:
        self.forest = [-1] * n

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x,y = y,x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

    def findRoot(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.findRoot(self.forest[x])
            return self.forest[x]

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)

    def size(self,x: int) -> int:
        return -self.forest[self.findRoot(x)]


n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
uf = UnionFind(n)
for ai,bi in ab:
    uf.union(ai-1,bi-1)
ans = 0
for i in range(n):
    ans = max(ans,uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(set)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
    
visited = set()

def dfs(node):
    
    c = 0
    stack = deque([node])
    visited.add(node)
    while stack:
        n = stack.popleft()
        c+=1
        for i in d[n]:
            if  i not in visited:
                visited.add(i)
                stack.append(i)
                
    return c
    

ans = 1

for key in list(d.keys()):
    if key not in visited:

        c = dfs(key)
        ans = max(ans, c)
        


print(ans)