Меня зовут Джим ди Гриз, я самый ловкий мошенник и авантюрист во всей галактике. По мотивам моих похождений написано множество книг, а ограблениям, совершённым мною, нет числа. Однако вы смогли застать меня в весьма неприятной ситуации.
Не обнаружив себя перед камерами, перехитрив десяток охранников и обойдя множество ловушек, я смог добраться до желанного ящика с сокровищами. Отворив его крышку, я активировал бомбу с часовым механизмом, который уже отсчитывает секунды до неминуемого взрыва! К счастью, мне уже приходилось сталкиваться с бомбами подобной модели, и я знаю, что часовой механизм можно остановить, если правильно соединить проводами контакты на панели управления.
Передо мной n контактов, соединённых n - 1 проводами. Контакты пронумерованы целыми числами от 1 до n. Бомба устроена таким образом, что если некоторый набор из k ≥ 2 контактов c1, c2, ..., ck соединён по циклу, то есть между парами контактов c1 и c2, c2 и c3, ..., ck и c1 есть k различных проводов, то срабатывает проверка безопасности, и заряд мгновенно детонирует, не оставляя от неудачливого взломщика и следа. В том числе, если два контакта соединены более чем одним проводом, то на них образуется цикл длины 2, и бомба также взрывается. Соединять контакт с самим собой запрещается.
С другой стороны, если я отсоединю одновременно более чем один провод (иными словами, в какой-то момент времени будет подключено менее n - 2 проводов), то сработает другая проверка безопасности, которая приведёт к такому же плачевному результату. Таким образом, всё, что мне остаётся, это последовательно вытаскивать провод и вставлять его в новое место, следя, чтобы не образовалось цикла, связывающего контакты.
Я знаю, как надо расположить провода, чтобы остановить часовой механизм. Но у меня остаётся всё меньше и меньше времени на это! Помогите мне выбраться из передряги: найдите кратчайшую последовательность безопасных операций, каждая из которых представляет собой отключение определённого провода и его подключение в новое место, а также выстраивает провода требуемым образом.
Выходные данные
В первой строке выведите число k (k ≥ 0) — минимальное количество проводов, которые потребуется переподключить.
В последующих k строках выведите четвёрки чисел ai, bi, ci, di, означающих, что на i-м шаге нужно отсоединить провод, соединяющий контакты ai и bi, и соединить им контакты ci и di. Разумеется, к этому моменту времени провод между контактами ai и bi должен присутствовать на схеме.
Если оптимальных последовательностей несколько, то выведите любую из них.
Если требуемой последовательности операций не существует, выведите одно число -1.