30066 - Sorting it all out

所谓升序排列,就是使用某种“小于”关系运算符,把各个不同的元素从小到大排好。例如,排列 A、B、C、D 表示 A < B、B < C 且 C < D。在本题中,我们会给出一组形如 A < B 的关系,请你判断这些关系是否已经足以确定一个升序排列。

输入

输入包含多个测试实例。每个实例首先占一行,包含两个正整数 nm。第一个数 n 表示需要排序的对象数量,满足 2 \le n \le 26。这些对象是大写字母表中最前面的 n 个字母。第二个数 m 表示本实例中给出的 A < B 形式的关系数量。

接下来有 m 行,每行包含一个这样的关系,由三个字符组成:一个大写字母、字符 < 和另一个大写字母。不会出现超出前 n 个字母范围的字母。

n = m = 0 时,表示输入结束。

输出

对于每个测试实例,输出一行,内容应为以下三种情况之一:

  1. Sorted sequence determined after xxx relations: yyy...y.

  2. Inconsistency found after xxx relations.

  3. Sorted sequence cannot be determined.

其中,xxx 表示在确定排序序列或发现矛盾时已经处理的关系数量——两种情况哪一种先发生,就以哪一种为准;yyy...y 表示确定的升序排列。

样例

输入

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.
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题