Graph bridges

Interview

Time limit1sMemory limit256 MB

Summary

Find every bridge in a connected undirected graph and print them sorted by endpoint.

Level: Medium4 of 10
Topics: DFS, Graph
Solved: No attempts yet

Problem

Given a graph, find every bridge and print them.

A bridge is an edge whose removal splits the graph into two or more parts. In other words, removing it increases the number of connected components.

Input

The first line has the number of vertices $V$ and the number of edges $E$ . ( $1 \le V \le 100\,000$ , $1 \le E \le 1\,000\,000$ )

Each of the next $E$ lines has two integers $A$ and $B$ , meaning that vertex $A$ and vertex $B$ are joined. Every edge is undirected.

The graph is always connected, no edge is given more than once, and $A$ and $B$ are never equal. Vertices are numbered from $1$ to $V$ .

Output

Print the number of bridges $K$ on the first line.

On each of the next $K$ lines print one bridge in the form A B with $A < B$ . Order the bridges by $A$ in increasing order, and by $B$ when $A$ ties. Print each edge only once. If $K$ is 0, print only the first line.

Examples7

Example 1

Input

Expected output

2
1 6
6 7

Example 2
Input
```
2 1
1 2
```
Expected output
```
1
1 2
```
Example 3
Input
```
5 5
1 2
2 3
3 4
4 5
5 1
```
Expected output
```
0
```
Example 4
Input
```
5 4
1 2
2 3
3 4
4 5
```
Expected output
```
4
1 2
2 3
3 4
4 5
```

Example 5

Input

Expected output

Example 6
Input
```
6 7
1 2
2 3
3 1
4 5
5 6
6 4
3 4
```
Expected output
```
1
3 4
```

Example 7

Input

Expected output