The city of Hiitsburgh has n light rail stations and m connections between them. Due to increased expenses in other building projects, the city council wants to reduce the maintenance costs of the light rail network by dismantling some of the connections such that at most 3n connections remain. Complicating the matter, they also want to ensure that the network remains reliable after dismantling the connections: If any two connections could fail in the initial network and there would still be a route between two stations, then that should still be true after dismantling the connections. Further, any pair of stations with a route between them should still have one afterwards.

Input

The first line of the input has two integers n and m.

The following m lines have two integers v and w, stating that there is a light rail connection between stations v and w.

Output

Output any valid set of light rail connections that can be kept. First, output the number of remaining connections and then the stations for each remaining connection on separate lines.

Constraints

• 1 \le n \le 10^3
• 0 \le m \le 10^4
• There is at most one direct connection between any pair of stations.

Example

Input:

5 8
1 2
1 3
1 4
2 3
2 4
3 4
3 5
2 5

Output:

7
1 2
1 3
1 4
2 3
2 4
3 4
3 5