题目描述

约翰的 $N$ 头牛排成一行挤奶时，有确定的顺序．牛被编成连续的号码 $1 \sim N$，他拥有 $L$ 条关于奶牛顺序的信息，所有的信息都写成「$A$ 在 $B$ 的前面」这样的形式，而且他知道最后一条是多余的。他觉得，有些冗余信息可以由其他信息推出，可以对这些信息进行精减。请帮助约翰删除尽可能多的冗余信息，但要保证能推出原有的顺序。可以保证的是，答案唯一，且最初的信息没有矛盾，如 $A$ 在 $B$ 前面，$B$ 在 $A$ 前面。

输入格式

第 $1$ 行：两个整数 $N$ 和 $L$。 第 $2$ 到 $L+1$ 行：每行两个整数 $X$ 和 $Y$，表示 $X$ 在 $Y$ 前。无重复。

输出格式

第 $1$ 行：整数 $U$ 。 第 $2$ 到 $U+I$ 行：输出精减后的信息，每行 $2$ 个数字，按第 $1$ 列数字排序。

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

4
2 1
3 5
4 2
5 2

提示

$3$ 在 $1$ 前，$4$ 在 $1$ 前可推。输出的每一行，不能被其他推出。

数据范围与约定

对于 $100\%$ 的数据，$1 ≤ N ≤ 1500, 1 ≤ X，y ≤ N$ 。

题目来源

Green