All Star

Обмеження: 2 сек., 512 МіБ

Somebody once told me...

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

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

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

Обмеження

\(3\leq n\leq 10^3\).

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 2 2 3 3 4 4 5	2 3 2 1 3 4 5

Примітки

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