公司的供应链

题目信息

时间限制: 1s

空间限制: 256M

输入文件: dag.in

输出文件: dag.out

题目描述

A 公司是 Earth 宇宙最大的工业产品公司，A 公司几乎垄断了 Earth 宇宙所有的工业品生产业务。Earth 宇宙目前一共有 $n$ 种不同的工业品，这些工业品囊括了 Earth 宇宙所有的原料、半成品、奢侈品等等。这些工业品之间的供应关系可以用一张有向图表示，图中的一条边 $(u, v)$ 表示 $u$ 工业品需要用于供应给 $v$ 工业品的生产。

因为一些众所周知的原因，A 公司的供应链随着时间推移越来越冗余，甚至工业品之间的供应关系出现了环！（多么不可思议啊）u 作为 A 公司的新晋股东，新官上任的第一把火就是缩减冗余的供应链！你需要保留一些供应关系，使得：

供应关系中不得有环，例如不可以工业品A供应工业品B，工业品B供应工业品C，而工业品C供应工业品A。
所有工业品的工业价值保持不变

每个工业品的工业价值定义为“供应它的工业品种类数”减去“它供应的工业品种类数”。

输入格式

第一行两个整数 $n,m$ 表示点数和边数。

接下来 $m$ 行，每行两个整数 $u,v$ 表示一条有向边。

保证不存在重边，自环。

输出格式

第一行一个整数 $m'$ 表示保留的供应链的边数。

接下来 $m'$ 行，每行两个整数，表示保留的边。

如有多个答案，任意输出一个即可。

样例

样例输入

样例输出

1
1 3

数据范围与提示

对于 $30\%$ 的数据， $n \leq 5, m \leq 10$ 。
对于 $60\%$ 的数据， $n \leq 1000, m\leq 2000$ 。
对于 $100\%$ 的数据， $1\leq n \leq 300000, 1\leq m\leq 600000$ 。
题目采用 Special Judge 评测。