#3466. 排序 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

给定 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.

数据范围与提示

,变量只可能为大写字母A~Z。