All Star#12970

All Star

2 секунди
512 мегабайтів
Складна

Somebody once told me...

У Шрека є вбиралень у його болоті, пронумерованих від до . Ці вбиральні з’єднані n - 1 двосторонніми дорогами так, що можна дістатися від будь-якої вбиральні до будь-якої іншої через кілька доріг.

За один хід Шрек може обрати три різні вбиральні , , такі, що існують дороги від до та від до , але немає дороги між та , і замінити дорогу, яка з’єднує та дорогою, що з’єднує та .

Відомо, що Шрек — зіркова особистість, тому він хоче, щоб його болото нагадувало зірку. Точніше він хоче виконати деяку кількість ходів так, щоб існувала вбиральня, яка з’єднана дорогами з усіма іншими.

Допоможіть йому знайти спосіб зробити це за мінімальну кількість ходів.

Вхідні дані

У першому рядку задано одне ціле число — кількість убиралень у Шрековому болоті.

У наступних n - 1 рядках задано по два числа та , які позначають, що між убиральнями та є дорога.

3\leq n\leq 10^3.

Можна показати, що при заданих обмеженнях, завжди існує розв’язок, який можна виконати не більше ніж за 10^6 ходів.

Вихідні дані

У першому рядку виведіть одне число — мінімальну кількість ходів, щоб перетворити болото Шрека на зірку.

У наступних рядках виведіть три цілих числа , і , які позначають, що Шрек повинен виконати описаний хід для вбиралень , і .

Якщо існує кілька можливих послідовностей ходів, ви можете вивести будь-яку з них.

Приклади

Приклад

Loading
Loading

Примітка

У наведеному прикладі після першого ходу вбиральня буде з’єднана дорогами з вбиральнями , і , а вбиральня буде з’єднана дорогою з убиральнею . Після другого ходу вбиральня матиме дороги, що з’єднують її з усіма іншими вбиральнями, і болото стане зіркою. Болото неможливо зробити зіркою за один хід, тому наведена відповідь є правильною.