Somebody once told me...
У Шрека є вбиралень у його болоті, пронумерованих від до . Ці вбиральні з’єднані n - 1 двосторонніми дорогами так, що можна дістатися від будь-якої вбиральні до будь-якої іншої через кілька доріг.
За один хід Шрек може обрати три різні вбиральні , , такі, що існують дороги від до та від до , але немає дороги між та , і замінити дорогу, яка з’єднує та дорогою, що з’єднує та .
Відомо, що Шрек — зіркова особистість, тому він хоче, щоб його болото нагадувало зірку. Точніше він хоче виконати деяку кількість ходів так, щоб існувала вбиральня, яка з’єднана дорогами з усіма іншими.
Допоможіть йому знайти спосіб зробити це за мінімальну кількість ходів.
У першому рядку задано одне ціле число — кількість убиралень у Шрековому болоті.
У наступних n - 1 рядках задано по два числа та , які позначають, що між убиральнями та є дорога.
3\leq n\leq 10^3.
Можна показати, що при заданих обмеженнях, завжди існує розв’язок, який можна виконати не більше ніж за 10^6 ходів.
У першому рядку виведіть одне число — мінімальну кількість ходів, щоб перетворити болото Шрека на зірку.
У наступних рядках виведіть три цілих числа , і , які позначають, що Шрек повинен виконати описаний хід для вбиралень , і .
Якщо існує кілька можливих послідовностей ходів, ви можете вивести будь-яку з них.
Приклад
У наведеному прикладі після першого ходу вбиральня буде з’єднана дорогами з вбиральнями , і , а вбиральня буде з’єднана дорогою з убиральнею . Після другого ходу вбиральня матиме дороги, що з’єднують її з усіма іншими вбиральнями, і болото стане зіркою. Болото неможливо зробити зіркою за один хід, тому наведена відповідь є правильною.