F. Стринг-арт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Начинающие художники-предприниматели Даня и Саша создают картины в технике стринг-арт. Картина в этой технике представляет собой $$$n$$$ гвоздиков, вбитых в специальную доску, $$$m$$$ пар которых соединены нитками. Чтобы картина выглядела как единое целое, от любого гвоздика до любого другого можно добраться по ниткам.

Даня и Саша хотят производить наборы для стринг-арта, которые позволят покупателю самому создать картину по инструкции. К сожалению, они выяснили, что если просто отправить клиенту $$$n$$$ гвоздиков, $$$m$$$ ниток и картинку, которую требуется получить, многие покупатели не справляются. Поэтому они решили продавать заготовки для картин.

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

Даня и Саша разработали очень красивую картину, теперь они хотят сделать для нее заготовку. Помогите им!

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

Первая строка ввода содержит два натуральных числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 2 \cdot 10^5$$$) — число гвоздиков на картине и число ниточек на ней.

Каждая из последующих $$$m$$$ строк содержит по два натуральных числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$) — номера гвоздиков соединённых соответствующей ниточкой. Никакая пара гвоздиков не соединена более, чем одной ниточкой, и никакой гвоздик не соединён ниточкой сам с собой. От любого гвоздика до любого можно добраться по ниточкам.

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

Выведите описание заготовки для картины.

Первая строка должна содержать одно натуральное числа $$$c$$$ — количество бусинок в заготовке.

Вторая строка должна содержать $$$c$$$ натуральных чисел $$$a_1, a_2, \ldots, a_c$$$ ($$$1 \leq a_i \leq n$$$) — цвета бусинок, при этом бусинки цвета $$$k$$$ будут прибиты к доске $$$k$$$-м гвоздиком в описанной во вводе картине.

Каждая из последующих $$$m$$$ строк должна содержать два натуральных числа — номера бусинок, соединённых очередной ниточкой. От каждой бусинки до каждой должен быть ровно один путь по ниточкам.

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

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