405011 - 唯一拓扑序

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列 A, B, C, D 表示 A < B, B < C, C < D。在这道题中,我们将给你一系列形如 A < B 的关系,并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入

第一行有两个正整数 n, m(2 ≤ n ≤ 26,1 ≤ m ≤ 600),n 表示需要排序的元素数量,第 1 到 n 个元素将用大写的 A, B, C, D, ... 表示。m 表示将给出的形如 A < B 的关系的数量。 接下来有 m 行,每行有 3 个字符,分别为一个大写字母,一个 < 符号,一个大写字母,表示两个元素之间的关系。

输出

若根据前 x 个关系即可确定这 n 个元素的顺序 yyy..y(如 ABC),输出 Sorted sequence determined after x relations: yyy...y. 其中 x 表示上述的前 x 个关系。 若根据前 x 个关系即发现存在矛盾(如 A < B, B < C, C < A),输出 Inconsistency found after x relations. 其中 x 表示的意义同上。 若根据这 m 个关系无法确定这 n 个元素的顺序,输出 Sorted sequence cannot be determined. (提示:确定 n 个元素的顺序后即可结束程序,可以不用考虑确定顺序之后出现矛盾的情况)

样例

输入

4 6
A<B
A<C
B<C
C<D
B<D
A<B

输出

Sorted sequence determined after 4 relations: ABCD.

输入

3 2
A<B
B<A

输出

Inconsistency found after 2 relations.

输入

26 1
A<Z

输出

Sorted sequence cannot be determined.
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题