Məsələlər
Побудова декомпозицiї
Побудова декомпозицiї
Знайдiть будь-який центроїд у деревi.
Giriş verilənləri
Перший рядок мiстить одне цiле число n(1 ≤ n ≤ 2 · 10^5) — кiлькiсть вершин.Кожен з наступних n − 1 рядкiв мiстить по два цiлi числа v_i та u_i(1 ≤ v_i , u_i ≤ n) — вершини, мiж якими iснує ребро.
Гарантується, що цей граф — дерево.
Çıxış verilənləri
У єдиному рядку виведiть номер вершини, яка є центроїдом. Якщо центроїдiв кiлька, то виведiть будь-який з них.
Nümunə
Giriş verilənləri #1
8 1 2 3 2 4 2 5 1 6 4 7 6 8 4
Çıxış verilənləri #1
BABBCCDC
Giriş verilənləri #2
7 1 2 1 3 1 4 5 2 6 3 7 4
Çıxış verilənləri #2
ABBBCCC