你们计算完后发现，幻想乡的基建甚至有高速公路，但是收费贵贵(Powered by 灵梦)。然而，高速公路尚未设立收费站，只有设立收费站后才能通行并调配食材。管理员幽幽子想把这个重要的任务交给你，如果耽误了幽幽子炫饭就会被幽幽子做成麻薯吃掉 （穿越三人集体波奇酱附体）。

有 $n$ 个地区，编号从 $1$ 开始。有 $m$ 条单向通行的道路。道路 $u\to v$ 表示只能从地区 $u$ 通向地区 $v$。定义从地区 $x$ 通往地区 $y$ 的路径是若干条不重道路的有序序列，满足首条道路起点为 $x$，最后一条道路终点为 $y$，其他道路的起点都是上一条道路的终点。例如若存在道路 $1\to3,3\to2,2\to4$ 则 $1\to 3\to2\to4$ 是地区 $1$ 到地区 $4$ 的一条路径。

现在一些道路上设置了收费站，使得对每条从地区 $1$ 通往地区 $n$ 的路径，路径上都存在且仅存在一条道路设置了收费站。且希望设置尽可能少的收费站达成上述目标。问至少需要设置多少个收费站，分别设置在哪些道路上。

输入一行两个整数 $n,m(2\le n\le10^5,1\le m\le10^5)$。

接下来输入 $m$ 行，每行两个整数 $u,v(1\le u,v\le n,u\neq v)$ 代表一条道路 $u\to v$。保证没有重边，不会成环，且存在至少一条从地区 $1$ 通往地区 $n$ 的路径，且保证对所有 $1 < x < n$，地区 $x$ 至少有一条路径为 $u\to x$ 和一条路径 $x\to v$。

输出一行一个整数，代表最小收费站个数 $k$。

接下来输入 $k$ 行，每行两个整数 $u,v(1\le u,v\le n)$，代表在道路 $u\to v$ 设置收费站。你可以用任意顺序输出道路。

如果有多个设置收费站的方案，你只需要输出任意一个即可。

对样例一，道路如图所示：

仅有两条 $1$ 到 $9$ 的路径即 $1\to2\to3\to5\to7\to8\to9,1\to2\to4\to6\to7\to8\to9$。因此，在 $1\to 2,7\to 8,8\to 9$ 三道路的其中一条设置收费站，均能满足目的。

对样例二，道路如图所示：

有四条 $1$ 到 $10$ 的道路。要设置最少的收费站，其中一个必须在 $5\to7,7\to 10$ 里选择，另一个在 $1\to4,4\to 6$ 里选择，共四种可行设置方案。

对样例三，道路如图所示：

唯一方案是在 $1\to 2$ 这条唯一道路设置收费站。