您所在城镇的议会决定改善道路标志的设置，特别是针对死胡同的标志。他们为您提供了一张道路地图，您需要确定在何处设置标志以标记死胡同。他们希望您使用的标志数量尽可能少。

道路地图是由多个地点和连接它们的双向街道组成的集合。以下规则描述了如何获得死胡同标志的完整布局。考虑一条连接地点 $x$ 和另一个地点的街道 $S$。如果从 $x$ 进入 $S$ 后，在不进行掉头的情况下无法回到 $x$，则 $S$ 的 $x$ 端入口处应设置一个死胡同标志。掉头是指立即反转方向的 180 度转弯。

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

图 E.1：样例输入示意图，标出了非冗余死胡同标志的放置位置。

输入格式

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

输出格式

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

样例

输入格式 1

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

输出格式 1

2
4 5
6 5

输入格式 2

8 8
1 2
1 3
2 3
3 4
1 5
1 6
6 7
6 8

输出格式 2

3
1 5
1 6
3 4