时间限制:1000 ms
内存限制:256 MiB
标准输入输出
题目类型:传统
评测方式:文本比较
给定 n 个变量,m 个不等式。
不等式之间具有传递性,即若 A>B 且 B>C ,则 A>C。
判断这 m 个不等式是否有矛盾。
若存在矛盾,则求出 t 的最小值,满足仅用前 t 个不等式就能确定不等式之间存在矛盾。
若无矛盾,则判断这 m 个不等式是否能确定每一对变量之间的关系。
若能,则求出 t 的最小值,满足仅用前 t 个不等式就能确定每一对变量之间的大小关系。
输入包含多组测试数据。
每组测试数据,第一行包含两个整数n和m。
接下来m行,每行包含一个不等式,不等式全部为小于关系。
当输入一行0 0时,表示输入终止。
每组数据输出一个占一行的结果。
结果可能为下列三种之一:
1、”Sorted sequence determined after t relations: yyy…y.”,其中yyy…y是指升序排列的所有变量。
2、”Sorted sequence cannot be determined.”。
3、”Inconsistency found after t relations.”。
样例输入
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
样例输出
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.