| Codeforces Round 345 (Div. 1) |
|---|
| Закончено |
Меня зовут Джим ди Гриз, я самый ловкий мошенник и авантюрист во всей галактике. По мотивам моих похождений написано множество книг, а ограблениям, совершённым мною, нет числа. Однако вы смогли застать меня в весьма неприятной ситуации.
Не обнаружив себя перед камерами, перехитрив десяток охранников и обойдя множество ловушек, я смог добраться до желанного ящика с сокровищами. Отворив его крышку, я активировал бомбу с часовым механизмом, который уже отсчитывает секунды до неминуемого взрыва! К счастью, мне уже приходилось сталкиваться с бомбами подобной модели, и я знаю, что часовой механизм можно остановить, если правильно соединить проводами контакты на панели управления.
Передо мной n контактов, соединённых n - 1 проводами. Контакты пронумерованы целыми числами от 1 до n. Бомба устроена таким образом, что если некоторый набор из k ≥ 2 контактов c1, c2, ..., ck соединён по циклу, то есть между парами контактов c1 и c2, c2 и c3, ..., ck и c1 есть k различных проводов, то срабатывает проверка безопасности, и заряд мгновенно детонирует, не оставляя от неудачливого взломщика и следа. В том числе, если два контакта соединены более чем одним проводом, то на них образуется цикл длины 2, и бомба также взрывается. Соединять контакт с самим собой запрещается.
С другой стороны, если я отсоединю одновременно более чем один провод (иными словами, в какой-то момент времени будет подключено менее n - 2 проводов), то сработает другая проверка безопасности, которая приведёт к такому же плачевному результату. Таким образом, всё, что мне остаётся, это последовательно вытаскивать провод и вставлять его в новое место, следя, чтобы не образовалось цикла, связывающего контакты.
Я знаю, как надо расположить провода, чтобы остановить часовой механизм. Но у меня остаётся всё меньше и меньше времени на это! Помогите мне выбраться из передряги: найдите кратчайшую последовательность безопасных операций, каждая из которых представляет собой отключение определённого провода и его подключение в новое место, а также выстраивает провода требуемым образом.
В первой строке входных данных находится число n (2 ≤ n ≤ 500 000) — количество контактов.
В каждой из последующих n - 1 строках записана пара целых чисел xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi), обозначающих номера контактов, соединённых очередным проводом в данный момент времени.
В последних n - 1 строках в аналогичном формате задаётся схема подключения проводов, останавливающая часовой механизм.
Гарантируется, что обе заданных схемы корректны (то есть, не содержат циклов и проводов, соединяющих контакт с самим собой).
В первой строке выведите число k (k ≥ 0) — минимальное количество проводов, которые потребуется переподключить.
В последующих k строках выведите четвёрки чисел ai, bi, ci, di, означающих, что на i-м шаге нужно отсоединить провод, соединяющий контакты ai и bi, и соединить им контакты ci и di. Разумеется, к этому моменту времени провод между контактами ai и bi должен присутствовать на схеме.
Если оптимальных последовательностей несколько, то выведите любую из них.
Если требуемой последовательности операций не существует, выведите одно число -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
Картинка с пояснением к тестам из условия:
