H. Дорожная задача
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В столице Берляндии (как вы хорошо знаете) n перекрестков, некоторые пары из которых соединены двусторонними дорогами. К сожалению, количество пробок в столице резко возросло, поэтому решено построить несколько новых дорог. Каждая новая дорога также должна соединять два перекрестка.

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

В городской сети дорог, как до реформы, так и после, между каждой парой перекрестков должно существовать не более одной дороги.

Входные данные

Первая строка входных данных содержит пару целых чисел n, m (2 ≤ n ≤ 900, 1 ≤ m ≤ 100000), где n — количество перекрестков, а m — количество дорог. Каждая из следующих m строк содержит описание одной дороги, которая задается номерами соединяемых перекрестков ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi). Перекрестки нумеруются от 1 до n. Из любого перекрестка города можно добраться в любой другой, передвигаясь по дорогам.

Выходные данные

В первую строку выведите t — количество добавленных дорог. Далее в t строках выведите описания добавленных дорог в формате входных данных. Вы можете использовать любой порядок для вывода как самих дорог, так и соединяемых каждой дорогой перекрестков. Если решений несколько, выведите любое.

Если столица не нуждается в реформе, выведите единственное число 0.

Если решения не существует, выведите единственное число -1.

Примеры
Входные данные
4 3
1 2
2 3
3 4
Выходные данные
1
1 4
Входные данные
4 4
1 2
2 3
2 4
3 4
Выходные данные
1
1 3