Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Дороги не только в Берляндии
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Правительство Берляндии решило улучшать отношения с соседними странами. В первую очередь было решено построить новые дороги так чтобы из всех городов Берляндии и соседних стран можно было добраться до всех остальных. Всего в Берляндии и соседних странах n городов и ровно n - 1 двусторонних дорог. Из-за недавнего финансового кризиса правительство Берляндии сильно стеснено в средствах, поэтому чтобы построить новую дорогу оно вынуждено закрывать какую-то из существующих. Каждый день можно закрыть одну существующую дорогу и сразу же построить новую. Ваша задача — определить, сколько дней потребуется для перестройки дороги так, чтобы из любого города можно было добраться до любого другого, а так же составить план закрытия старых и постройки новых дорог.

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

В первой строке записано целое число n (2 ≤ n ≤ 1000) — число городов в Берляндии и соседних странах. Далее в n - 1 строках записаны описания дорог. Каждая дорога описывается двумя целыми числами ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — пара городов, которые дорога соединяет. Между каждой парой городов не может быть больше одной дороги, никакая дорога не соединяет город сам с собой.

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

Выведите ответ на задачу, число t — какое наименьшее число дней потребуется, чтобы перестроить дороги так чтобы из любого города можно было добраться до любого другого. Далее выведите t строк — план закрытия старых и постройки новых дорог. Каждая строка должна описывать действия в очередной день в формате i j u v — означает, что нужно закрыть дорогу между городами i и j и построить дорогу между городами u и v. Города нумеруются начиная с 1. Если решений несколько, выведите любое.

Примеры
Входные данные
2
1 2
Выходные данные
0
Входные данные
7
1 2
2 3
3 1
4 5
5 6
6 7
Выходные данные
1
3 1 3 7