Задача K. Великолепный Гоша ≡

Условие

Телефонист Гоша получил задание соединить дома оптоволоконным кабелем по заданной схеме. На схеме указаны дома и их соединения между собой. При этом, согласно схеме может требоваться соединить два дома несколькими кабелями.

Когда Гоша приехал на работу, он обнаружил, что схему оставил дома. Однако, у него оказались записи, фиксирующие, сколько кабелей должно быть подведено к каждому из домов. Он попытался восстановить схему, соединяя дома с использованием только имеющихся записей. По окончании работ оказалось, что получившаяся сеть схеме не соответствует. На рис. 1 показаны пример схемы и сети, реализованной Гошей.

На следующий день Гоша стал исправлять свою работу, глядя на верную схему. По техническим причинам он вынужден ограничиться последовательным выполнением операций только одного типа. В результате одной такой операции удаляются два кабеля, соединяющих некоторые две пары различных домов (см. рис. 2а), и эти же четыре дома соединяются либо как показано на рис. 2б, либо так, как на рис. 2в. Заметим, что после любой из таких операций количество кабелей, подведенных к каждому из домов, не меняется.

Требуется написать программу, которая определяет, сможет ли Гоша за один рабочий день перестроить сеть согласно схеме, если за один день он выполняет не более 48 000 операций. Если такая перестройка возможна, то программа должна выдать соответствующую последовательность операций.

Формат входного файла

В первой строке входного файла задано число N (4 ≤ N ≤ 1 000) — количество домов на схеме.

Во второй строке записано число M (2 ≤ M ≤ 20 000)  — количество кабелей в схеме.

В следующих M строках расположены пары номеров домов, соединенных кабелями на схеме. Дома имеют номера от 1 до N.

Затем в M строках указаны пары номеров домов, которые Гоша соединил кабелями.

Формат выходного файла

Если перестроить сеть согласно схеме невозможно, или для перестройки сети требуется более 48 000 операций, то выходной файл должен содержать только число -1. В противном случае выходной файл должен содержать описание последовательности операций, по одной операции в строке.

Каждая операция описывается начальным и конечным положением кабелей. Сначала четырьмя целыми числами V₁, V₂, V₃, V₄ записывается исходное положение кабелей, при этом один из кабелей соединяет дома с номерами V₁, V₂, а другой — V₃, V₄. Затем в таком же формате описывается конечное положение.

Примеры тестов

6
6
1 2
2 3
1 4
2 5
5 4
5 6
1 4
1 4
2 5
3 6
2 5
5 2

1 4 5 2 1 2 5 4
2 5 3 6 2 3 5 6