В некотором государстве король подсчитал собранные налоги и решил пустить их на ремонт дорог. Всего в том королевстве было N городов, которые соединялись M двусторонними дорогами таким образом, что из любого города можно было проехать в любой другой. Дорожная сеть находилась в катастрофическом состоянии, поэтому король решил, пока еще собранные деньги не обесценились, починить за лето как можно большее количество дорог. Жители королевства возмутились тем, что все пути, которыми они пользовались ежедневно, будут закрыты на лето. Поэтому королю пришлось пойти на уступки, пообещав, что для любого города будет закрыто на ремонт не более одной дороги, выходящей из него. Помогите королю выполнить свой план, не вызвав недовольства со стороны жителей.

В первой строке расположены через пробел два целых числа: N и M (2 ≤ N ≤ 10⁵, M = N − 1). В следующих M строках описываются дороги королевства в виде пар (a_i, b_i) — номеров городов, соединяемых очередной дорогой (1 ≤ a_i, b_i ≤ N).

В первой строке выведите целое число K — максимальное число дорог, которые можно закрыть на ремонт, не вызвав беспорядков в народе. В следующих K строках выведите описание дорог в том же формате, в каком оно было приведено во входных данных.