/** čĊ Ġ* Ġ@ author : Ġtour ist čĊ Ġ*/ čĊč Ċ import Ġjava . io .* č Ċ import Ġjava . util .* čĊč Ċ var Ġg Ġ= ĠArray < ArrayList < Int >>( 0 , Ġ{_ Ġ-> ĠArrayList < Int >() }); č Ċ var Ġwas Ġ= ĠBoolean Array ( 0 ) čĊč Ċ fun Ġdfs ( v : ĠInt ) Ġ: ĠInt Ġ{ čĊĠĠĠ Ġwas [ v ] Ġ= Ġtrue čĊĠĠĠ Ġvar Ġcnt Ġ= Ġg [ v ]. size () čĊĠĠĠ Ġvar Ġa Ġ= ĠArrayList < Int >() čĊĠĠĠ Ġfor Ġ( j Ġin Ġ 0 .. cnt - 1 ) Ġ{ čĊĠĠĠĠĠĠĠ Ġvar Ġu Ġ= Ġg [ v ]. get ( j ) čĊĠĠĠĠĠĠĠ Ġif Ġ(! was [ u ]) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġa . add ( dfs ( u )) čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠ Ġ} čĊĠĠĠ Ġif Ġ( a . size () Ġ<= Ġ 1 ) Ġ{ čĊĠĠĠĠĠĠĠ Ġreturn Ġ 1 čĊĠĠĠ Ġ} čĊĠĠĠ ĠCollections . sort ( a ) čĊĠĠĠ Ġreturn Ġ 1 Ġ+ Ġa [ a . size () Ġ- Ġ 2 ] Ġ+ Ġa [ a . size () Ġ- Ġ 1 ] č Ċ } čĊč Ċ fun Ġsolve ( sc : ĠInput Reader , Ġout : ĠPrintWriter ) Ġ{ čĊ ĉ val Ġtest Cases Ġ= Ġsc . nextInt () čĊ ĉ for Ġ( test Ġin Ġ 1 .. test Cases ) Ġ{ čĊĉ ĉ out . print (" Case Ġ#$ test : Ġ") čĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġsc . nextInt () čĊĠĠĠĠĠĠĠ Ġg Ġ= ĠArray < ArrayList < Int >>( n , Ġ{_ Ġ-> ĠArrayList < Int >() }); čĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. n - 2 ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfoo Ġ= Ġsc . nextInt () Ġ- Ġ 1 čĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbar Ġ= Ġsc . nextInt () Ġ- Ġ 1 čĊĠĠĠĠĠĠĠĠĠĠĠ Ġg [ foo ]. add ( bar ) čĊĠĠĠĠĠĠĠĠĠĠĠ Ġg [ bar ]. add ( foo ) čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġwas Ġ= ĠBoolean Array ( n ) čĊĠĠĠĠĠĠĠ Ġvar Ġans Ġ= Ġ 0 čĊĠĠĠĠĠĠĠ Ġfor Ġ( st Ġin Ġ 0 .. n - 1 ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. n - 1 ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwas [ i ] Ġ= Ġfalse čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcur Ġ= Ġdfs ( st ) čĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Ġ> Ġans ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġans Ġ= Ġcur čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġout . println ( n Ġ- Ġans ) čĊ ĉ } č Ċ } čĊč Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ čĊĠĠĠ Ġval Ġtask Name Ġ= Ġ" b " čĊ ĉ var Ġinput : ĠInputStream Ġ= ĠSystem .` in ` čĊ ĉ var Ġoutput : ĠOutputStream Ġ= ĠSystem . out čĊ ĉ val Ġfile Ġ= ĠFile (" src /" Ġ+ Ġtask Name Ġ+ Ġ"/ in ") čĊ ĉ if Ġ( file . can Read ()) Ġ{ čĊĉ ĉ input Ġ= ĠFileInputStream ( file ) čĊĉ ĉ output Ġ= ĠFileOutputStream (" src /" Ġ+ Ġtask Name Ġ+ Ġ"/ out ") čĊ ĉ } čĊ ĉ val Ġsc Ġ= ĠInput Reader ( input ) čĊ ĉ val Ġout Ġ= ĠPrintWriter ( output ) čĊ ĉ solve ( sc , Ġout ) čĊ ĉ out . close () č Ċ } čĊč Ċ class ĠInput Reader Ġ( r : ĠInputStream ) Ġ{ čĊ ĉ private Ġval Ġbr Ġ= ĠBufferedReader ( InputStream Reader ( r )) čĊ ĉ private Ġvar Ġst : ĠString Tokenizer ? Ġ= Ġnull čĊčĊ ĉ fun Ġnext Token (): ĠString ? Ġ{ čĊĉ ĉ while Ġ( st Ġ== Ġnull Ġ|| Ġ! st !!. hasMore Tokens ()) Ġ{ čĊĉĉ ĉ val Ġline Ġ= Ġbr . readLine () čĊĉĉ ĉ if Ġ( line Ġ== Ġnull ) Ġ{ čĊĉĉĉ ĉ return Ġnull čĊĉĉ ĉ } čĊĉĉ ĉ st Ġ= ĠString Tokenizer ( line ) čĊĉ ĉ } čĊĉ ĉ return Ġst !!. nextToken () čĊ ĉ } čĊčĊĠĠĠ Ġfun Ġnext Int (): ĠInt Ġ{ čĊĠĠĠĠĠĠĠ Ġreturn Ġnext Token () !!. toInt () čĊĠĠĠ Ġ} čĊčĊĠĠĠ Ġfun Ġnext Long (): ĠLong Ġ{ čĊĠĠĠĠĠĠĠ Ġreturn Ġnext Token () !!. to Long () čĊĠĠĠ Ġ} čĊčĊ ĉ fun Ġnext Double (): ĠDouble Ġ{ čĊĉ ĉ return Ġnext Token () !!. toDouble () čĊ ĉ } č Ċ } čĊ