Капитан Флинт не зря стал прославленной грозой пиратов. Всё дело в том, что он уже в детстве придумывал планы ограблений, мечтал о том, куда хочет потратить сокровища и какую память о себе хочет оставить. И вот, юный капитан Флинт придумал себе интересную задачку, которую он быстро решил. А сможете ли вы повторить решение грозы 52 морей?
Дано $$$n$$$ островов. Известно, что пираты могут перемещаться напрямую только между $$$m$$$ парами островов (это обусловлено особенностями рельефа — корабль с большим количеством сокровищ в некоторых местах может сесть на дно), при этом известно, что $$$m \lt n$$$. Вот только с годами капитан Флинт стал совсем забывчив и не помнит, между какими именно парами островов мог передвигаться его грозный корабль. Но вот что капитан Флинт помнит — так это то, что для каждой пары островов существовало не более 1 пути, по которому можно добраться от первого острова до второго (иными словами, в графе, в котором вершины — это острова, а рёбра — возможные прямые перемещения между островами, нет циклов).
Так как плавать от одного острова к другому — недешёвое удовольствие, то гроза всех морей хочет оценить минимальное суммарное расстояние между каждой парой островов (если между ними, конечно, существует путь) — пираты хотят как можно меньше средств потратить на топливо, которое уйдёт на поездки между островами. Старина Флинт к этому моменту забыл даже начало условия задачи, поэтому вам придётся помочь тем пиратам, кто ещё хоть что-то помнит, и подсказать им, между какими парами островов им можно перемещаться напрямую, чтобы минимизировать суммарное расстояние между каждой парой островов. Если вы не справитесь, то капитан Флинт вспомнит прошлое и начнёт пальбу по вам, поэтому советуем поторопиться!
Во входной строке вводятся два числа $$$n$$$ и $$$m$$$, разделённые пробелом: $$$n$$$ — количество островов, между которыми плавал капитан Флинт, $$$m$$$ — количество пар островов, между которыми мог проходить корабль пиратов ($$$2 ≤ n ≤ 10^5, 1 ≤ m \lt n$$$).
Выведите $$$m$$$ строк, в $$$i$$$-й из которых содержатся два числа — $$$a_i, b_i$$$, означающие, что пиратам можно будет напрямую путешествовать между островами $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$). Обратите внимание, что суммарное расстояние между каждой парой островов должно быть минимально.
Обратите внимание на Примечание.
4 2
1 2 3 4
5 3
1 2 1 3 4 5
В первом тестовом примере из условия мы можем «разместить» $$$2$$$ прямых перемещения между островами так, чтобы они не имели общего острова (как это сделано в ответе), и получим сумму расстояний: $$$1 + 1 = 2$$$. Если же они будут иметь общий остров (например, «разместим» прямые перемещения между островами $$$1$$$ и $$$2$$$, а также между островами $$$1$$$ и $$$3$$$), то сумма расстояний будет равна: $$$1 + 1 + 2 = 4$$$ (указаны расстояния между островами $$$1$$$ и $$$2$$$, между островами $$$1$$$ и $$$3$$$, между островами $$$2$$$ и $$$3$$$).
Во втором тестовом примере пиратам можно перемещаться напрямую только между островами $$$1$$$ и $$$2$$$, между островами $$$1$$$ и $$$3$$$, между островами $$$4$$$ и $$$5$$$. Отсюда следует, что сумма расстояний между каждой парой островов равна: $$$1 + 1 + 2 + 1 = 5$$$ (указаны расстояния между островами $$$1$$$ и $$$2$$$, между островами $$$1$$$ и $$$3$$$, между островами $$$2$$$ и $$$3$$$, между островами $$$4$$$ и $$$5$$$).
