Дорожні роботи
У певній державі король підрахував зібрані податки і вирішив витратити їх на ремонт доріг. У цьому королівстві є N міст, з'єднаних M двосторонніми дорогами так, що з будь-якого міста можна дістатися до будь-якого іншого. Дорожня мережа перебуває у жахливому стані, тому король вирішив, поки зібрані кошти не знецінилися, відремонтувати якомога більше доріг за літо. Жителі королівства обурилися, що всі дороги, якими вони користуються щодня, будуть закриті на літо. Тому король був змушений піти на поступки, пообіцявши, що для будь-якого міста буде закрито на ремонт не більше однієї дороги, що виходить з нього.
Допоможіть королю реалізувати свій план, не викликавши невдоволення серед жителів.
Вхідні дані
У першому рядку через пробіл подано два цілі числа: N і M (2 ≤ N ≤ 10^5, M = N−1). У наступних M рядках описані дороги королівства у вигляді пар (a_i, b_i) — номери міст, що з'єднуються відповідною дорогою (1 ≤ a_i, b_i ≤ N).
Вихідні дані
У першому рядку виведіть ціле число K — максимальну кількість доріг, які можна закрити на ремонт, не викликавши обурення серед населення. У наступних K рядках виведіть опис доріг у тому ж форматі, в якому вони були наведені у вхідних даних.