5. Bezkonkurenčná manufaktúra

V dnešnej zúboženej ekonomike sa možno iba ťažko na niečo spoľahnúť. Jednou výnimkou tohoto pravidla je však nemenný dopyt po sršňom mede. Ten ako jediný zostal neovplyvnený, po tom, čo nedávne udalosti postihli už aj ziskovosť produkcie pavúčieho medu.

Vašej sršnej farme sa už dlhšiu dobu darí náramne dobre. Morálka je vysoká, produkcia je bezproblémová a výrobok je kvalitný. Sršne sú vďaka desiatkam hodín nadštandardného tréningu schopné a vysoko zorganizované. Na rozdiel od včiel majú sršne vďaka svojej vyššej inteligencii rádovo väčší potenciál, ktorý má v kombinácii s poctivým prvotriednym tréningom za následok pedantne efektívnu Lean-Agile manufaktúru s rozsiahlou hierarchiou vedenia. Primitívny pôvod včelieho medu je v porovnaní na smiech.

Úloha

Výroba špičkového sršnieho medu je vysoko technická záležitosť založená na častej komunikácii. Tá prebieha iba v rámci hierarchie. Teda každý sršeň vie komunikovať iba so svojím priamym nadriadeným alebo podriadenými, pričom na umožnenie komunikácie ľubovoľnej dvojice sršňov bol zavedený systém preposielania správ. Sršnia hierarchia samozrejme umožňuje komunikáciu ľubovolným dvom sršňom a to dokonca unikátnym najkratším spôsobom. V hierarchii sa teda nevyskytujú cykly, keďže v internom testovaní sa ukázalo, že ich prítomnosť síce občas skrátila čas dodania správy, avšak pridaná komplexita narúšala sršňom pracovný flow.

Tento systém doteraz fungoval bezchybne. Máte však obavy o jeho dlhodobom vplyve na niektorých jedincov. V hierarchii sa vyskytuje niekoľko sršňov, ktoré slúžia ako nevyhnutný spostredkovateľ komunikácie veľkého množstva dvojíc. Dokonca ste zistili, že v nej existuje jeden sršeň, ktorý je najvyťaženejší zo všetkých a o ktorého máte preto najväčšie obavy. Ste teda ochotní umožniť komunikovať jednej ľubovoľnej dodatočnej dvojici sršňov, aby ste ho aspoň trochu odbremenili. Zaujímalo by vás, koľko dvojíc využíva tohoto sršňa ako sprostredkovateľa a koľko najmenej dvojíc ho bude stále nutne využívať po tom, čo umožníte komunikáciu jednej dodatočnej dvojici (výber dvojice nechávame na vaše uváženie). Vašou úlohou bude túto analýzu efektívne vykonať na všetkých manufaktúrach vašej farmy.

Formát vstupu

Na vstupe bude na prvom riadku číslo \(2 \leq N \leq 100001\) označujúce počet sršňov v práve analyzovanej manufaktúre. Nasleduje \(N-1\) riadkov popisujúcich hierarchiu sršňov - na každom z nich dve čísla \(0 \leq A, B < N\) symbolizujúce susednosť sršňov \(A\) a \(B\) v rámci hierarchie. Hierarchia na vstupe je súvislá a bez cyklov. Sršeň \(0\) je vedúcim manufaktúry a existuje práve jeden najvyťaženejší sršeň.

Formát výstupu

Na výstup vypíšte na práve jeden riadok práve dve celé čísla v desiatkovej sústave oddelené práve jednou medzerou. Prvé číslo je počet dvojíc sršňov, ktoré nutne komunikujú cez najvyťaženejšieho sršňa a druhé číslo je to isté, avšak v prípade umožnenia komunikácie jednej dodatočnej dvojici.

Príklady

Input:

7
0 1
1 2
2 3
2 4
4 5
4 6

Output:

11 5

Sršeň 2 je navyťaženejší. Po tom, čo umožníme komunikovať napríklad sršňom 0 a 6, už bude sršeň 2 nutne sprostredkovávavávať iba komunikáciu sršňa 3 so všetkými ostatnými (avšak pri komunikácii sršnov 2 a 3 neslúži sršeň 2 ako sprostredkovateľ).