问题 1123 --确定排序序列

1123: 确定排序序列

时间限制: 1 Sec  内存限制: 32 MB
提交: 38  解决: 11
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

一个由不同的值组成的按升序排序的序列,通常使用小于操作符,把元素从小到大排列。
例如,有序序列A,B,C,D表示A<B,B<C和C<D。
现给你一组形如A<B的关系,请你确定是否已经形成一个排序的序列。

输入

输入包含多组测试数据。每组输入的第一行是两个正整数n和m。
n表示排序对象的个数,2<=n<=26。排序对象是字母表开始的n个大写字符。
m表示形如A<B的关系的个数。
接下来m行,每行输入一个关系,由三个字符构成:第一个大写字母,符号“<”,第二个大写字母。字母不会超过字母表开始的n个字母的范围。
当n=m=0时,输入结束。

输出

对于每组输入,输出一行。该行将是以下三者之一:
Sorted sequence determined after xxx relations: yyy...y.(在xxx个关系后,确定了排序序列:yyy...y)
Sorted sequence cannot be determined.(不能确定排序序列)
Inconsistency found after xxx relations.(在xxx个关系后,发现关系矛盾)

解释说明:
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.

提示

来源

[提交][状态]