Codeforces Beta Round 25 (Див. 2) |
---|
Закончено |
Правительство Берляндии решило улучшать отношения с соседними странами. В первую очередь было решено построить новые дороги так чтобы из всех городов Берляндии и соседних стран можно было добраться до всех остальных. Всего в Берляндии и соседних странах 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
Название |
---|