- Time limit: 1.00 s
- Memory limit: 512 MB
A road is called necessary if there is no route between some two cities after removing that road. Your task is to find all necessary roads.
Input
The first input line has two integers $n$ and $m$: the number of cities and roads. The cities are numbered $1,2,\dots,n$.
After this, there are $m$ lines that describe the roads. Each line has two integers $a$ and $b$: there is a road between cities $a$ and $b$. There is at most one road between two cities, and every road connects two distinct cities.
Output
First print an integer $k$: the number of necessary roads. After that, print $k$ lines that describe the roads. You may print the roads in any order.
Constraints
- $2 \le n \le 10^5$
- $1 \le m \le 2 \cdot 10^5$
- $1 \le a,b \le n$
Input:
5 5
1 2
1 4
2 4
3 5
4 5
Output:
2
3 5
4 5