Задача №113893. Часовой механизм
Меня зовут Джим ди Гриз, я самый ловкий мошенник и авантюрист во всей галактике. По мотивам моих похождений написано множество книг, а ограблениям, совершённым мною, нет числа. Однако вы смогли застать меня в весьма неприятной ситуации.
Не обнаружив себя перед камерами, перехитрив десяток охранников и обойдя множество ловушек, я смог добраться до желанного ящика с сокровищами. Отворив его крышку, я активировал бомбу с часовым механизмом, который уже отсчитывает секунды до неминуемого взрыва! К счастью, мне уже приходилось сталкиваться с бомбами подобной модели, и я знаю, что часовой механизм можно остановить, если правильно соединить проводами контакты на панели управления.
Передо мной n контактов, соединённых n - 1 проводами. Контакты пронумерованы целыми числами от 1 до n . Бомба устроена таким образом, что если некоторый набор из k ≥ 2 контактов c 1 , c 2 , ..., c k соединён по циклу, то есть между парами контактов c 1 и c 2 , c 2 и c 3 , ... , c k и c 1 есть k различных проводов, то срабатывает проверка безопасности, и заряд мгновенно детонирует, не оставляя от неудачливого взломщика и следа. В том числе, если два контакта соединены более чем одним проводом, то на них образуется цикл длины 2 , и бомба также взрывается. Соединять контакт с самим собой запрещается.
С другой стороны, если я отсоединю одновременно более чем один провод (иными словами, в какой-то момент времени будет подключено менее n - 2 проводов), то сработает другая проверка безопасности, которая приведёт к такому же плачевному результату. Таким образом, всё, что мне остаётся, это последовательно вытаскивать провод и вставлять его в новое место, следя, чтобы не образовалось цикла, связывающего контакты.
Я знаю, как надо расположить провода, чтобы остановить часовой механизм. Но у меня остаётся всё меньше и меньше времени на это! Помогите мне выбраться из передряги: найдите кратчайшую последовательность безопасных операций, каждая из которых представляет собой отключение определённого провода и его подключение в новое место, а также выстраивает провода требуемым образом.
В первой строке входных данных находится число n ( 2 ≤ n ≤ 500 000 ) — количество контактов.
В каждой из последующих n - 1 строках записана пара целых чисел x i , y i ( 1 ≤ x i , y i ≤ n , x i ≠ y i ), обозначающих номера контактов, соединённых очередным проводом в данный момент времени.
В последних n - 1 строках в аналогичном формате задаётся схема подключения проводов, останавливающая часовой механизм.
В первой строке выведите число k ( k ≥ 0 ) — минимальное количество проводов, которые потребуется переподключить.
В последующих k строках выведите четвёрки чисел a i , b i , c i , d i , означающих, что на i -м шаге нужно отсоединить провод, соединяющий контакты a i и b i , и соединить им контакты c i и d i . Разумеется, к этому моменту времени провод между контактами a i и b i должен присутствовать на схеме.
Если оптимальных последовательностей несколько, то выведите любую из них.
Если требуемой последовательности операций не существует, выведите одно число -1 .
Тесты к этой задаче состоят из шести групп. Баллы за группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп, за исключением, возможно, тестов из условия.
Картинка с пояснением к тестам из условия:
3 1 2 2 3 1 3 3 2
1 1 2 1 3
4 1 2 2 3 3 4 2 4 4 1 1 3
3 1 2 1 3 4 3 4 1 2 3 2 4