bzoj#P3355. [USACO2004 Jan] 有序奶牛

[USACO2004 Jan] 有序奶牛

题目描述

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

输入格式

11 行:两个整数 NNLL。 第 22L+1L+1 行:每行两个整数 XXYY,表示 XXYY 前。无重复。

输出格式

11 行:整数 UU 。 第 22U+IU+I 行:输出精减后的信息,每行 22 个数字,按第 11 列数字排序。

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

提示

3311 前,4411 前可推。输出的每一行,不能被其他推出。

数据范围与约定

对于 100%100\% 的数据,1N1500,1XyN1 ≤ N ≤ 1500, 1 ≤ X,y ≤ N

题目来源

Green