Dead-End Detector

Source: Wikimedia Commons
The road map is a collection of locations connected by two-way streets. The following rule describes how to obtain a complete placement of dead-end signs. Consider a street $S$ connecting a location $x$ with another location. The $x$-entrance of $S$ gets a dead-end sign if, after entering $S$ from $x$, it is not possible to come back to $x$ without making a U-turn. A U-turn is a $180$-degree turn immediately reversing the direction.
To save costs, you have decided not to install redundant dead-end signs, as specified by the following rule. Consider a street $S$ with a dead-end sign at its $x$-entrance and another street $T$ with a dead-end sign at its $y$-entrance. If, after entering $S$ from $x$, it is possible to go to $y$ and enter $T$ without making a U-turn, the dead-end sign at the $y$-entrance of $T$ is redundant. See Figure 1 for examples.
![]() |
(a) Sample Input 1 |
![]() |
(b) Sample Input 2 |
Input
The first line of input contains two integers $n$ and $m$, where $n$ ($1 \leq n \leq 5 \cdot 10^5$) is the number of locations and $m$ ($0 \leq m \leq 5 \cdot 10^5$) is the number of streets. Each of the following $m$ lines contains two integers $v$ and $w$ ($1 \leq v < w \leq n$) indicating that there is a two-way street connecting locations $v$ and $w$. All location pairs in the input are distinct.
Output
On the first line, output $k$, the number of dead-end signs installed. On each of the next $k$ lines, output two integers $v$ and $w$ marking that a dead-end sign should be installed at the $v$-entrance of a street connecting locations $v$ and $w$. The lines describing dead-end signs must be sorted in ascending order of $v$-locations, breaking ties in ascending order of $w$-locations.
Sample Input 1 | Sample Output 1 |
---|---|
6 5 1 2 1 3 2 3 4 5 5 6 |
2 4 5 6 5 |
Sample Input 2 | Sample Output 2 |
---|---|
8 8 1 2 1 3 2 3 3 4 1 5 1 6 6 7 6 8 |
3 1 5 1 6 3 4 |