Мер міста Гадюкіно вирішив перевірити стан доріг після щойно проведеного капітального ремонту. Для цього він хоче проїхати кожною дорогою в обох напрямках.

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

У місті Гадюкіно \(n\) перехресть і \(m\) доріг, кожна з яких з'єднує два різні перехрестя. Між двома перехрестями може бути не більше однієї дороги.

Відомо, що дорогами від кожного перехрестя можна доїхати до будь-якого іншого.

Формат вхідних даних

Вхідний потік містить цілі числа \(n\) та \( m\) \((1≤n≤10^4\), \(1≤m≤10^5)\), і далі \(m\) пар цілих чисел \(a_i\) і \(b_i\) - номери перехресть, які з'єднує i дорога.

Формат вихідних даних Виведіть число \(s\) — мінімальну довжину колії та далі \(s + 1\) число — номери перехресть у тому порядку, в якому їх потрібно проїжджати.

Приклад вхідних даних

3 3
1 2
2 3
1 3

Приклад вихідних даних

6
1 3 2 1 2 3 1