[Usaco2004 Jan]有序奶牛

时间限制:10s      空间限制:128MB

题目描述

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


输入格式

 
    第1行:两个整数N和L.
    第2到L+1行:每行两个整数X和Y(1≤X,y≤N),表示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前可推.输出的每一行,不能被其他推出.


题目来源

Green

Menuappsclose