До торжественного открытия небоскрёба Исеть осталось совсем немного, а в здании ещё не проведена компьютерная сеть, которую планировали сделать надёжной и разветвлённой. Всего в здании имеется N узлов, которые требуется объединить в сеть. Предполагалось соединить их с помощью M прямых каналов, при этом между каждой парой узлов могло быть не более одного прямого канала. Для экономии времени было решено сначала смонтировать только минимально необходимое количество соединений, так чтобы сеть была связной, а остальные закончить уже после торжественного открытия. Но, чтобы сеть работала быстрее, было поставлено условие: среди всех возможных конфигураций сети выбрать ту, в которой наибольшее расстояние между узлами было бы минимальным. Расстоянием между узлами называется количество промежуточных узлов на пути от одного к другому.

Первая строка содержит целые числа N (2 ≤ N ≤ 100) и M (1 ≤ M ≤ 10000). В следующих M строках описан первоначальный план сети в виде пар узлов, которые надо соединить напрямую. В каждой из этих строк содержатся номера узлов, которые соединяются очередным прямым каналом. Узлы занумерованы от 1 до N. Гарантируется, что сеть по плану является связной и никакой канал не соединяет некоторый узел сам с собой.

Выведите новый план сети в том же формате.