题目描述

约翰的$\red{N(1≤}$$\red{N≤}$$\red{1500)}$头牛排成一行挤奶时，有确定的顺序．牛被编成连续的号码$\red{1}$$\red{...N,}$他拥有$\red{L}$条关于奶牛顺序的信息，所 有的信息都写成"$\red{A}$在$\red{B}$的前面"这样的形式，而且他知道最后一条是多余的．

他觉得，有些冗余信息可以由其他信息推出，可以对这些信息进行精减．

请帮助约翰删除旧能多的冗余信息，但要保证能推出原有的顺序．可以保证的是，答案唯一，且最初的信息没有矛盾，如$\red{A}$在$\red{B}$前面，$\red{B}$在$\red{A}$前面 ．

输入格式

第$\red{1}$行：两个整数$\red{N}$和$\red{L}$．

第$\red{2}$到$\red{L+1}$行：每行两个整数$\red{X}$和$\red{Y(1≤}$$\red{X，}$$\red{y≤}$$\red{N)，}$表示$\red{X}$在$\red{Y}$前．无重复．

输出格式

第$\red{1}$行：整数$\red{U.}$

第$\red{2}$到$\red{U+I}$行：输出精减后的信息，每行$\red{2}$个数字，按第$\red{1}$列数字排序．

样例

输入样例

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

输出样例

4
2 1
3 5
4 2
5 2

提示

$\red{3}$在$\red{1}$前，$\red{4}$在$\red{1}$前可推．输出的每一行，不能被其他推出．