题目背景

Warning: If you submit a malicious program, you will be banned.

警告：恶意提交本题将被封号。

题目描述

The council of your home town has decided to improve road sign placement,especially for dead ends. They have given you a road map, and you must determine where to put up signs to mark the dead ends. They want you to use as few signs as possible.

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 E.1 for examples.

Figure E.1: Illustration of sample inputs, indicating where non-redundant dead-end signs are placed.

输入格式

The first line of input contains two integers $n$ and $m$, where $n$ $(1 \leq n \leq 5\times10^5)$ is the number of locations and $m$ $(0 \leq m \leq 5 \times 10^5)$ is the number of streets. Each of the following $m$ lines contains two integers $v$ and $w$ $(1 \leq v \lt w \leq n)$ indicating that there is a two-way street connecting locations $v$ and $w$. All location pairs in the input are distinct.

输出格式

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.

题目大意

有一张 $n$ 个点 $m$ 条边的简单无向图。

如果走过一条边 $u→v$ 后，不掉头无法返回到 u，这条边就是对 $u$ 来说的“死路”。

你需要对每个死路标记路标，但是有的路标是多余的。

如果从一个死路 $u→v$ 开始可以不掉头地走到另一个死路 $u' → v'$，那么后者 $u' → v'$ 就是多余的。

最后问要标记多少路标，输出每对 $u→v$，按照 $u$ 为第一关键字，$v$ 为第二关键字排序。

第一行输入 $n$ , $m$ ，后 $m$ 行每行两个整数 $u$ , $v$ 。

输出的第一行是要标记的路标数 $k$ ，然后 $k$ 行每行一对题目所说的死路 ： $u→v$ （不要输出“$→$”）。

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

2
4 5
6 5

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

提示

Source: ICPC World Finals 2019 Problem E.