Dead End Sign Placement

The council of your home town wants to install dead‐end signs on streets in a cost‐efficient way. You are given a road map with n locations and m two‐way streets. For every street S that connects location (x) with another location, the complete (but redundant) placement rule is: place a dead‐end sign at the x–entrance of S if, after entering S from (x), it is not possible to return to (x) without making an immediate 180° turn (a U–turn).

To save costs, you decide not to install redundant signs. The redundancy rule is: if a dead–end sign is placed at the x–entrance of street S and another dead–end sign is placed at the y–entrance of street T, and if after entering S from (x) it is possible to reach y and enter T (without an immediate U–turn), then the sign at y is redundant. In other words, in any chain of bridges (streets whose removal disconnects the graph) only the sign at the outermost dead–end is needed.

It can be shown that the minimal (non–redundant) placement is obtained by considering the following: first, a complete placement installs a sign at the entrance of a street if and only if the street is a bridge in the road network. Then, contract every maximal 2–edge–connected subgraph (i.e. remove non–bridge edges) to obtain a tree (called the bridge tree). In this tree every leaf component corresponds to a dead–end. For each leaf component, let the incident bridge connect a vertex in that component with a vertex in another component; a sign is then needed at the vertex in the leaf component.

Given the road map, compute all non–redundant dead–end sign placements. Each sign is denoted by a pair (u) and (v), meaning a sign is placed at the (u)–entrance of the street connecting (u) and (v). The output should be sorted in lexicographical order (first by (u), then by (v)).

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵), representing the number of locations and the number of two–way streets, respectively.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) indicating a street connecting locations u and v. There is at most one street between any pair of locations.

outputFormat

First, output an integer k representing the number of dead–end signs that need to be installed. Then output k lines, each containing two integers u and v, meaning that a dead–end sign should be installed at the u–entrance of the street connecting u and v.

The output pairs must be sorted in lexicographical order (first by u, then by v).

sample

4 3
1 2
2 3
3 4

2
1 2
4 3