Ayna Ağacı?

MIRROR-TREE-CHECK (MT Check), Link-Cut planet sistemlərinin qapılarında klassik bir CAPTCHA-dır. Bu, sadəcə bir ağacı ayna simmetriyası üçün yoxlamaq deməkdir.

İşte ağacı ayna simmetriyası üçün proses:

1. İki vertex $v$ və $u$ seçin ($v$-$u$ yoluna görə ayna simmetriyası).

2. Ağacı vertex $v$-dən asın.

3. $v$-dən $u$-ya olan yol üzərindəki hər bir vertex üçün, əgər o vertexin alt ağacında $u$ yoxdursa, hər bir uşağın alt ağacının bir nüsxəsini yaratın və onları eyni vertexə qoşun.

Biz bu prosesi $f(t,v,u)$ kimi göstərəcəyik, ki, bu da ağacı $t$-ni $v$-$u$ yoluna görə ayna simmetriyası üçün aynalama deməkdir.

İşte 1-ci və 10-cu vertex arasında olan yola görə verilmiş ağacın aynalanması üçün nümunə:

Verilmiş ağac

Yeni ağac, mavi vertexlər əlavə edilən vertexləri göstərir

Ağac $g$ aynalanmış adlanır əgər başqa bir ağac $t$ və onun iki vertexi $x$ və $y$ seçə bilərsək, ki, ağac $g$ və ağac $f(t,x,y)$ oxşar olsun.

Biz iki ağacı oxşar hesab edirik əgər bu iki ağacın vertexlərinin nömrələrini dəyişdirərək bu iki ağacın kəsirlərinin cədvəlləri eyni olsun.

Siz bu tapşırıq üçün hazırlanmışdınız, amma şeytan Chmyaks sizi yeni bir hile ilə şaşırttı. Qapıların üzərində büyü edərək, giriş ağacına bir yaprak əlavə etdi. Artıq qapılar heç kimi içərinə buraxmayacaq.

Siz hələ dəsizdiniz ki, nəinki, birdən-birə büyücü Frusi göründü və sizə kömək etməyə gəldi. Frusi güclü büyüyə malikdir və büyüyü pozmağa cəhd edə bilər, amma bunu etmək üçün, Chmyaksın əlavə etdiyi yaprağı çıxarmaq lazımdır. Hər bir yaprağı yoxlamaq çox uzun vaxt alar və çox çox mana tələb edər (hətta Frusi də belə çox mana yoxdur). Neylər ki, bizim büyücü büyünü tanıdı və sizə bir yan təsir haqqında məlumat verdi: yaprağın əlavə edilmədən əvvəlki ağacın əlbətdən aynalanmış olduğunu.

Frusi artıq büyülərini hazırlayır və sizin tapşırığınız bütün potensial yaprakları tapmaq üçün hazırlanır (məsələn, ağacın aynalanmasından sonra ağacın aynalanmasına görə çıxarılacaq bütün bu cür yapraklar, bundan sonra kötü vertex adlanır) ya da göstərin ki, Frusi haradasa səhv edib və belə zirvələr yoxdur.

Giriş verilənləri

Birinci sətir bir tam ədəd $n(2\le n\le 2\cdot 10^5)$ içərir — ağacın vertexlərinin sayı. Növbəti $n-1$ sətirdən hər biri iki tam ədəd $x_i$ və $y_i(1\le x_i,y_i\le n)$ içərir — $x_i$ və $y_i$ arasındakı kəsiş. Bu kəsirlərin ağacı təşkil etdiyi təmin edilir.

Çıxış verilənləri

Birinci sətirdə bütün bu təpələrin sayını və ya belə təpələr yoxdursa $0$-ı çap edin.

İkinci sətirdə bütün təpələri artan qaydada çap edin və ya belə təpələr yoxdursa, heç nə çap etməyin.

Nümunələr