Dekompazisiyanın qurulması#10159

Dekompazisiyanın qurulması

2 saniyə

488,385 meqabayt

Asan

Mərkəz dekompozisiyasını qurun.

Birinci səviyyənin zirvəsi $« A »$ , ikinci səviyyənin zirvəsi $« B »$ və s. olmalıdır...

Giriş formatı

Birinci sətir bir tam ədəd $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n (1 ≤ n ≤ 2 · 10^5) — zirvələrin sayını ehtiva edir.

Növbəti $n - 1$ n − 1 sətirin hər biri iki tam ədəd $v_{i}$ v_i və $u_{i}$ u_i $(1 \leq v_{i}, u_{i} \leq n)$ (1 ≤ v_i, u_i ≤ n) ehtiva edir, bu da $u_{i}$ u_i və $v_{i}$ v_i zirvələri arasında bir kənarın olduğunu göstərir.

Çıxış formatı

n simvoldan ibarət bir sətir çıxarın.Əgər bir neçə cavab varsa, onlardan hər hansı birini çıxarın.

Nümunələr

Nümunə 1

Loading

Nümunə 2

Loading

n (1 \leq n \leq 2 \cdot 1 0^{5})

n - 1

v_{i}

u_{i}

(1 \leq v_{i}, u_{i} \leq n)

u_{i}

v_{i}