Дан заданный граф-дерево. Добавьте как можно больше рёбер так, чтобы итоговый граф был кактусом.

Кактус — это граф, в котором каждое ребро принадлежит не более чем одному простому циклу. В графе не должно быть петель или кратных рёбер.

Входные данные

В первой строке содержится целое число $N$, размер дерева ($1 \le N \le 200\,000$).

Каждая из следующих $N - 1$ строк содержит два целых числа $u$ и $v$ ($1 \le u, v \le N, u \neq v$), указывающих на наличие ребра между узлами $u$ и $v$. Гарантируется, что исходный граф является деревом.

Выходные данные

В первой строке выведите $K$, максимальное количество рёбер, которые можно добавить в граф. В каждой из следующих $K$ строк выведите два целых числа $a$ и $b$ ($1 \le a, b \le N, a \neq b$), указывающих на то, что вы добавляете ребро между узлами $a$ и $b$. Итоговый граф должен быть кактусом.

Если существует несколько решений с максимально возможным $K$, выведите любое из них.

Примеры

Входные данные 1

6
6 4
3 1
3 6
4 5
2 3

Выходные данные 1

2
2 1
3 5