CSES - Necessary Roads
  • Time limit: 1.00 s
  • Memory limit: 512 MB

There are nn cities and mm roads between them. There is a route between any two cities.

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 nn and mm: the number of cities and roads. The cities are numbered 1,2,,n1,2,\dots,n.

After this, there are mm lines that describe the roads. Each line has two integers aa and bb: there is a road between cities aa and bb. There is at most one road between two cities, and every road connects two distinct cities.

Output

First print an integer kk: the number of necessary roads. After that, print kk lines that describe the roads. You may print the roads in any order.

Constraints

  • 2n1052 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Example

Input:

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

Output:

2
3 5
4 5