Demux Problems Submissions Users Contests Log in Sign up


Critical Trade Bridge


Submit solution

Points: 100
Time limit: 8.0s
Memory limit: 98M

Author:
Problem type
Allowed languages
C, C++, Java, Python

There are n islands from 0 to n-1. And the trades between these islands is mainly through the bridges connecting them.

All the islands are connected, i.e., there will always be a path between any two islands. There can be multiple paths as well.

Let's say there are islands A and B. And there is a direct bridge between A and B. If we remove this bridge, and if the trade between A and B is cut. Then such a bridge is called critical bridges.

Your task is to find all such bridges.

Example:

Graph.png

In the above graph, Bridge 1 and 2 is a critical because if it is disconnected then trade between 1 and 2 is cut.

Bridge between 2 and 3 is not critical because if it is disconnected then trade still continues through (2 -> 4 -> 3).

Input

The first line contains n and e where n represents number of islands, e represents number of bridges.

Next e lines contains two integers u, v. This represents there is a bridge between u and v.

Output

The first line should contain c -- number of critical bridges

The next c lines contains two integers u, v. This represents bridge between u and v is a critical bridge. u \(\lt\) v

Note

  • You must print answer in sorted order

Example: If critical bridges are: [(5, 7), (2, 1), (1, 0)]

Then you should print then as: [(0, 1), (1, 2), (5, 7)]

Constraints

1 \(\leq\) n \(\leq 10^5\)

n-1 \(\leq\) e \(\leq 10^5\)

Example

Input

4 4
0 1
1 2
2 3
1 3

Output

1
0 1

Comments