Велике крадівництво

Обмеження: 2 сек., 256 МіБ

В Україні міста з’єднані двосторонніми дорогами. Між кожною парою міст є не більше ніж одна дорога. Також дорога не може вести від міста до самого себе. Однак між деякими містами може не бути шляху, навіть транзитного через інші міста.

ЗЕник узявся виправляти ситуацію. Він хоче, щоб із кожного міста можна було доїхати дорогами до будь-якого іншого (можливо, через інші міста), тому почав будувати дороги між деякими парами міст.

Сивочолий гетьман стверджує, що Зеник не будує нові дороги, а краде старі та переміщує їх. Зеник начебто може вкрасти дорогу, що з’єднує міста \(u\) та \(v\), та прокласти її між містами \(u\) та \(w\), якщо між ними ще нема дороги. За словами гетьмана, Зеник може так робити багато разів.

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

Вхідні дані

У першому рядку містяться два цілих числа \(n\) і \(m\) — кількість міст та доріг в Україні відповідно.

Кожен з наступних \(m\) рядків містить по два цілих числа \(u\) й \(v\) — номери міст, які з’єднує відповідна дорога. Міста пронумеровані цілими числами від 1 до \(n\).

Вихідні дані

У першому рядку виведіть ціле число \(k\) — мінімальну необхідну кількість крадіжок.

У наступних \(k\) рядках виведіть по три цілих числа \(u\), \(v\) та \(w\), які описують відповідну крадіжку — крадіжка дороги між містами \(u\) та \(v\) і прокладання дороги між містами \(u\) та \(w\). На момент крадіжки повинна бути дорога між \(u\) й \(v\) і не повинно бути дороги між \(u\) й \(w\).

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

Обмеження

\(1 \le n \le m \le 10^5\),

\(1 \le u, v, w \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11 11 1 5 1 8 1 9 2 6 2 7 3 10 3 11 4 10 4 11 5 9 6 7	2 4 11 7 9 1 4

Примітки

У заданому тесті Зеник виконує дві крадіжки. Спочатку він забирає дорогу між містами 4 та 11 і замінює її дорогою, що сполучає міста 4 та 7. Далі він замінює дорогу (9, 1) на дорогу (9, 4). Після виконання цих двох крадіжок усі пари міст будуть зв’язаними між собою.