405432: GYM101962 D Carnival

The Carnival is the biggest street festival in Soteropolis. It occurs in the very beginning of every Soteropolitan year and attracts a lot of people from around the globe. For the citizens of Soteropolis, though, it is actually a 50-50 situation: half of them love it, half of them hate it. That mainly occurs because it gets hard to transit in the city during the festival.

The mayor is planning to hold some tests before the actual Carnival. These tests are usually very small festivals which take place in a street of Soteropolis. During a festival, the street where it takes place gets blocked. Some of the streets of the city are called critical, but first we need to understand how the road system of Soteropolis was designed.

Soteropolis is composed by $$$n$$$ junctions directly connected by $$$m$$$ one-way streets. A street $$$(u, v)$$$ means that a car can go from $$$u$$$ to $$$v$$$ but not the other way around. Also, Soteropolis was carefully designed such that from every junction it's possible to get to every other junction using the existent streets. A critical street is a street that, when blocked, makes it impossible to get from some junction $$$u$$$ to some other junction $$$v$$$.

The mayor wants to hold a test festival. Your task is to decide which roads are critical and should be avoided.

The first line contains two integers $$$n, m$$$ ($$$2 \leq n \leq 2000; 1 \leq m \leq 50000$$$) – the number of junctions and the number of streets, respectively.

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains two integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n; u_i \neq v_i$$$) – meaning that this is an one-way road between $$$u_i$$$ and $$$v_i$$$. You may assume that the vertices are numbered from 1 to $$$n$$$.

There can be two or more streets between the same pair of junctions.

In the first line output an integer $$$k$$$ – the number of critical streets.

In the next $$$k$$$ lines output the junctions connected by each of the streets. Each line should contain a pair of integers separated by space. Note those are ordered pairs since the streets are one-way, but the pairs themselves may be printed in any order.

3 3
1 2
2 3
3 1

3
1 2
2 3
3 1

4 6
1 2
2 3
3 4
4 1
2 4
3 1

3
1 2
2 3
4 1