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

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

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

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

Формат ввода В первой строке заданы через пробел два числа: $n\left(3 \leq n \leq 10^{5}\right)$ - количество датацентров (пронумерованы с единицы) и $k\left(n-1 \leq k \leq 10^{5}\right)$ - количество соединений датацентров.

В следующих $k$ строках перечислены соединения: два числа $i$ и $j$ через пробел - это значит что датацентры под номерами $i$ и $j$ соединены кабелем.

Формат вывода В первой строке выведите число $m$ - минимальное количество новых соединений которые нужно сделать чтобы при любом однократном обрыве сеть оставалась связной. В следующих $m$строках выведите пары чисел разделенных пробелом - номера датацентров которые нужно соединить друг с другом кабелем.