Critical Pipelines

In the land of Cahoots, Lomikel, the god of pipelines, manages everything from water conduits to sewer tunnels, connecting many holy springs via an intricate network. During the annual ritual led by the Supreme Plumber, water must be routed through the pipelines. However, sometimes a pipeline fails and not all pipes have alternative routes. Such pipelines are called critical pipelines (or bridges) since they are the only connection between two parts of the network.

Your task is to help the Plumber find all the bridges in the given undirected graph. The graph contains N nodes and M edges and may be disconnected, where each connected component is considered a subgraph. A pipeline (edge) is a bridge if and only if its removal increases the number of connected components.

Memory Limit: 16 MB.

Note that the graph uses 1-indexed vertices. For each bridge, output the two endpoints (with the smaller vertex first). First, output the total count of bridges, and then output each bridge on a new line; the bridges should be sorted in increasing order (first by the first vertex and then by the second vertex).

In algorithmic terms, you can use the following formulas in LaTeX format for DFS timing:

\( disc[u] = time \) and \( low[u] = \min \{ disc[u], low[v] \} \) for each child \( v \) of \( u \).

inputFormat

The first line contains two integers N and M denoting the number of vertices and edges respectively.

Each of the following M lines contains two integers u and v denoting an edge between nodes u and v.

outputFormat

Output the number of bridges on the first line. Then output each bridge on a new line as two space-separated integers representing the endpoints. The endpoints in each bridge should appear in increasing order and the list of bridges should be sorted by the first endpoint, and then by the second.

sample

3 3
1 2
2 3
1 3

0