Правительство Берляндии решило улучшать отношения с соседними странами. В первую очередь было решено построить новые дороги так чтобы из всех городов Берляндии и соседних стран можно было добраться до всех остальных. Всего в Берляндии и соседних странах n городов и ровно n - 1 двусторонних дорог. Из-за недавнего финансового кризиса правительство Берляндии сильно стеснено в средствах, поэтому чтобы построить новую дорогу оно вынуждено закрывать какую-то из существующих. Каждый день можно закрыть одну существующую дорогу и сразу же построить новую. Ваша задача — определить, сколько дней потребуется для перестройки дороги так, чтобы из любого города можно было добраться до любого другого, а так же составить план закрытия старых и постройки новых дорог.
Выходные данные
Выведите ответ на задачу, число t — какое наименьшее число дней потребуется, чтобы перестроить дороги так чтобы из любого города можно было добраться до любого другого. Далее выведите t строк — план закрытия старых и постройки новых дорог. Каждая строка должна описывать действия в очередной день в формате i j u v — означает, что нужно закрыть дорогу между городами i и j и построить дорогу между городами u и v. Города нумеруются начиная с 1. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
0
|
|
2
|
7
1 2
2 3
3 1
4 5
5 6
6 7
|
1
3 1 3 7
|