package Ġcom . radix 2 . algorithms . extras Ċ Ċ import Ġkotlin . collections .* Ċ Ċ class ĠWeight ed Quick Union With Path Compression UF < T Ġ: ĠAny > Ġ{ ĊĊĠĠĠ Ġprivate Ġval Ġmap Ġ= Ġmutable Map Of < T , ĠMetadata < T >>() ĊĊĠĠĠ Ġprivate Ġclass ĠMetadata < E Ġ: ĠAny > Ġ{ ĊĠĠĠĠĠĠĠ Ġlateinit Ġvar Ġparent : ĠE ĊĠĠĠĠĠĠĠ Ġvar Ġsize Ġ= Ġ 1 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġunion ( p : ĠT , Ġq : ĠT ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġp Root Ġ= Ġroot ( p ) ĊĠĠĠĠĠĠĠ Ġvar Ġq Root Ġ= Ġroot ( q ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ( p Root Ġ== Ġq Root ) Ġreturn Ġmap [ p Root ] !!. size ĊĊĠĠĠĠĠĠĠ Ġif Ġ( map [ p Root ] !!. size Ġ< Ġmap [ q Root ] !!. size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= Ġp Root ĊĠĠĠĠĠĠĠĠĠĠĠ Ġp Root Ġ= Ġq Root ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq Root Ġ= Ġtemp ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġmap [ q Root ] !!. parent Ġ= Ġp Root ĊĠĠĠĠĠĠĠ Ġmap [ p Root ] !!. size Ġ+= Ġmap [ q Root ] !!. size ĊĊĠĠĠĠĠĠĠ Ġreturn Ġmap [ p Root ] !!. size ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġsize ( p : ĠT ): ĠInt Ġ= Ġmap [ root ( p )] !!. size ĊĊĠĠĠ Ġprivate Ġfun Ġroot ( p : ĠT ): ĠT Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġmetadata Ġ= Ġget Metadata ( p ) ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( metadata . parent Ġ!= Ġmap [ metadata . parent ] !!. parent ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmetadata . parent Ġ= Ġmap [ map [ metadata . parent ] !!. parent ] !!. parent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmetadata Ġ= Ġmap [ metadata . parent ] !! ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġmetadata . parent ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget Metadata ( p : ĠT ): ĠMetadata < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! map . contains ( p )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmetadata Ġ= ĠMetadata < T >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmetadata . parent Ġ= Ġp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmetadata . size Ġ= Ġ 1 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġmap [ p ] Ġ= Ġmetadata ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġmap [ p ] !! ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠ Ġval Ġstart Ġ= ĠSystem . nano Time () ĊĊĠĠĠ Ġval Ġreader Ġ= ĠSystem .` in `. buffered Reader () ĊĊĠĠĠ Ġvar Ġ(_, Ġq ) Ġ= Ġreader . readLine (). split (" Ġ"). map Ġ{ Ġit . toInt () Ġ} ĊĊĠĠĠ Ġval Ġu f Ġ= ĠWeight ed Quick Union With Path Compression UF < String >() ĊĊĠĠĠ Ġwhile Ġ( q -- Ġ> Ġ 0 ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġline Ġ= Ġreader . readLine () ĊĊĠĠĠĠĠĠĠ Ġif Ġ( line . startsWith (" M ")) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( p 1 , Ġp 2 ) Ġ= Ġline . substring ( 2 ). split (" Ġ"). map Ġ{ Ġit . toInt () Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġu f . union ( p 1 . toString (), Ġp 2 . toString ()) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġline . substring ( 2 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ("${ uf . size ( p . toString ()) }") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreader . close () ĊĊĠĠĠ Ġval Ġend Ġ= ĠSystem . nano Time () ĊĊĠĠĠ Ġprintln ("${ end Ġ- Ġstart }") Ċ }