#P3355. [Usaco2004 Jan]有序奶牛
[Usaco2004 Jan]有序奶牛
[USACO 2004 Jan] 有序奶牛
题目描述
约翰的 头奶牛排成一行挤奶,编号 到 。约翰掌握 条形如“奶牛 在奶牛 前面”的信息。这些信息没有矛盾,最后一条可以由其他信息推出。
约翰想删除尽可能多的信息,使原来的每条信息都仍可从保留的信息推出。例如,若已知 在 前、 在 前,则可推出 在 前。求应该保留哪些信息。答案唯一。
输入格式
从标准输入读入。第一行是两个整数 。接下来 行,每行两个整数 ,表示奶牛 在奶牛 前。信息互不重复。
输出格式
向标准输出输出。第一行是一个整数 ,表示保留的信息数。接下来 行,每行输出一条保留的信息 。先按 从小到大排列;若 相同,再按 从小到大排列。
5 6
3 5
4 2
5 2
2 1
3 1
4 1
4
2 1
3 5
4 2
5 2
提示
样例中, 在 前、 在 前都可以从保留的信息推出。四条保留的信息都不能由其余保留信息推出。
数据范围与约定
,。