题目描述

你所在家乡的市政委员会决定改善道路标志的设置，特别是对于死胡同的标志。他们给了你一张道路地图，你需要确定在哪里设置标志来标记死胡同。他们希望你使用尽可能少的标志。

这张道路地图是由通过双向街道连接的多个地点组成的。以下规则描述了如何完成死胡同标志的设置。考虑一条街道 $S$ 连接地点 $x$ 和另一个地点。如果从 $x$ 进入 $S$ 后，无法在不掉头的情况下返回 $x$，则在 $S$ 的 $x$ 入口处设置一个死胡同标志。掉头是指立即反向的 180 度转弯。

为了节省成本，你决定不安装冗余的死胡同标志，具体规则如下。考虑一条在 $x$ 入口处有死胡同标志的街道 $S$ 和另一条在 $y$ 入口处有死胡同标志的街道 $T$。如果从 $x$ 进入 $S$ 后，可以在不掉头的情况下到达 $y$ 并进入 $T$，那么 $T$ 的 $y$ 入口处的死胡同标志是冗余的。参见图 E.1 以获取示例。

图 E.1：示例输入的说明，指示放置非冗余死胡同标志的位置。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，其中 $n$ $(1 \leq n \leq 5\times10^5)$ 是地点的数量，$m$ $(0 \leq m \leq 5 \times 10^5)$ 是街道的数量。接下来的 $m$ 行中的每一行包含两个整数 $v$ 和 $w$ $(1 \leq v < w \leq n)$，表示有一条双向街道连接地点 $v$ 和 $w$。输入中的所有地点对都是不同的。

输出格式

第一行输出 $k$，表示安装的死胡同标志的数量。在接下来的 $k$ 行中，每行输出两个整数 $v$ 和 $w$，表示在连接地点 $v$ 和 $w$ 的街道的 $v$ 入口处应安装一个死胡同标志。描述死胡同标志的行必须按 $v$ 位置升序排序，若有相同则按 $w$ 位置升序排序。

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

提示

来源：ICPC 世界总决赛 2019 问题 E。

题面翻译由 ChatGPT-4o 提供。