eolymp
bolt
Try our new interface for solving problems
Məsələlər

Побудова декомпозицiї

Побудова декомпозицiї

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 488 MiB

Знайд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ть будь-який з них.

A.png

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