7. Kreslenie stromov

“Let’s make some happy little trees,” povedal Bob Ross¹ a začal kresliť stromy na plátno. Inšpirovaná týmto známym umelcom, zobrala Paulínka svoje obľúbené voskovky a začala kresliť stromy na papier.

Paulínka rada kreslí zakorenené informatické stromy, a aby bol výsledný obrázok čo najkrajší, musia byť všetky stromy rôzne a zároveň musia všetky pochádzať z rovnakého materského stromu. (Potom môže obdivovateľom umenia hovoriť, že stromy majú spoločnú dušu.) V časti úloha hneď vysvetlíme, čo to znamená.

Pomôžte Paulínke zistiť, koľko najviac stromov, môže nakresliť, aby splnila želané podmienky. A nezabudnite, keby sa vám to aj na prvý pokus nepodarilo, Bob Ross má pre vás jednu múdrosť: “We don’t make mistakes, we have happy accidents.”

Úloha

Informatický strom (ďalej len strom) je množina \(n\) vrcholov a \(n-1\) hrán, taká, že z každého vrcholu do každého vedie práve jedna cesta. Zakorenený informatický strom (ďalej len zakorenený strom) je strom, v ktorom sme jeden vrchol vybrali ako koreň.

Zo stromu vieme vytvoriť \(n\) zakorenených stromov tak, že postupne označíme každý z \(n\) vrcholov ako koreň (viď obrázok pri prvom príklade vstupu).

Pre tieto zakorenené stromy si zavedieme nový pojem, rovnakosť, ku ktorému opačný pojem je rôznosť. Zakorenené stromy budeme volať rovnaké, keď sa líšia len v označení vrcholov a v poradí synov každého vrcholu. T.j. pokiaľ dovolíme ľubovoľne prehadzovať poradie synov, vieme pretvoriť jeden strom na druhý. Pokiaľ sa takto nedajú pretvoriť, tak uvažujeme, že sú stromy rôzne.

Formálna definícia by mohla byť nasledovná: Dva zakorenené stromy voláme rovnaké, ak existuje bijektívne zobrazenie² \(f\) vrcholov jedného stromu na vrcholy druhého stromu, také že pre všetky \(x,y\) platí, že \(x\) je otec \(y\) práve vtedy, keď \(f(x)\) je otec \(f(y)\).

Na obrázkoch môžeme vidieť príklady troch stromov, z ktorých prvé dva sú rovnaké a tretí je od oboch rôzny. Zobrazenie, ktoré spĺňa formálnu definíciu je \(1,2,3,4,5,6,7,8 \rightarrow 8,7,6,5,4,1,2,3\), ale aj \(1,2,3,4,5,6,7,8 \rightarrow 8,7,6,5,4,3,2,1\)

Na vstupe máte zadaný strom. Vypíšte koľko najviac navzájom rôznych zakorenených stromov môžeme dostať označením niektorého vrcholu tohto stromu ako koreň.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) – počet vrcholov zadaného stromu. Vrcholy sú očíslované \(1\) až \(n\).

Na nasledujúcich \(n-1\) riadkoch su vymenované hrany zadaného stromu, na každom riadku sú čísla dvoch vrcholov, \(a_i, b_i\), ktoré táto hrana spája. \(1\leq a_i, b_i \leq n\)

Formát výstupu

Na výstup vypíšte jedno číslo – počet rôznych zakorenených stromov, ktoré dostaneme, ak postupne každý z vrcholov označíme ako koreň.

Hodnotenie

Je 8 sád vstupov. Platia v nich nasledovné obmedzenia:

Príklady

Input:

4
1 2
2 3
3 4

Output:

2

Ak strom zakoreníme za prvý alebo posledný vrchol, dostaneme rovnaký strom. Podobne dostaneme rovnaké stromy, ak ho zakoreníme za druhý alebo tretí. Vieme teda nakresliť dva rôzne zakorenené stromy.

Na obrázku nižšie môžeme vidieť, aké stromy dostaneme, pokiaľ zakoreníme vstupný strom postupne vo vrcholoch \(1, 2, 3, 4\)

Input:

11
1 2
2 3
3 4
4 5
4 6
4 7
5 10
10 9
10 8
7 11

Output:

10

Input:

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

Output:

7