В городе готовятся к большому ночному празднику. На площади установлено n кварталов, пронумерованных от 1 до n. Нужно проложить световые дорожки между кварталами так, чтобы по ним можно было быстро передавать сигнал на включение иллюминации.

Однако часть пар кварталов нельзя соединять напрямую: для некоторых пар установка световой дорожки запрещена.

Ваша задача — построить минимальное количество световых дорожек так, чтобы:

• ни одна построенная дорожка не соединяла запрещённую пару кварталов;
• из любого квартала можно было добраться до любого другого, пройдя не более чем по двум дорожкам.

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

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

В первой строке записаны два целых числа n и m — количество кварталов и количество запрещённых пар (2 <= n <= 1000, 0 <= m <= 10000).

В следующих m строках записаны по два целых числа a и b — номера кварталов, которые нельзя соединять напрямую (1 <= a, b <= n, a != b).

Гарантируется, что каждая запрещённая пара задана не более одного раза.

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

В первой строке выведите одно целое число k — минимальное количество дорожек.

В следующих k строках выведите по два целых числа u и v — кварталы, между которыми нужно построить дорожку.

Если существует несколько подходящих ответов, выведите любой из них.

Пример 1

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

4 2
1 2
2 3

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

3
4 1
4 2
4 3

Пример 2

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

5 0

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

4
1 2
1 3
1 4
1 5

Пример 3

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

6 3
1 2
1 3
1 4

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

5
5 1
5 2
5 3
5 4
5 6