Once upon a time there was a king. One day the king counted up the collected taxes and decided to spend the money for the road maintenance. There were N cities in that kingdom and M two-way roads connected them in such way that one could travel from a city to others using these roads. The road network was catastrophic without repairing, so the king made up his mind to repair as many roads as possible during the summer, before the money depreciated. The inhabitants of the kingdom were shocked to know that all the ways they used to go would be blocked for summer. So the king promised that at most one road from a city would be blocked. Help the king to fulfil his plan without displeasing the citizens.

The first line of input contains two natural numbers N and M (2 ≤ N ≤ 10⁵, M = N − 1), separated with a space. Each of the next M lines describes a road in the form (a_i, b_i), where a_i and b_i are numbers of the cities connected with i'th road (1 ≤ a_i, b_i ≤ N).

The first line of output should contain the only integer K being the maximum number of roads that the king can close for maintenance without raising disorders in his kingdom. The next K lines should describe these roads in the same form as they were given in the input.