BZPRO
#3355. [Usaco2004 Jan]有序奶牛
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
约翰的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前可推．输出的每一行，不能被其他推出．
BZPRO