Description

An ascending sorted sequence of distinct values is one in which some form of a less-than Operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this PRoblem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy…y.

Sorted sequence cannot be determined.

Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.

Sample Input

Sample Output

題意

依序給出一些字母之間的大小關系，判斷并輸出它能否唯一確定一個序列滿足這一關系。

思路

依舊是一道拓撲排序的題目。

無法唯一確定一個序列當且僅當在所有關系輸入完畢之后，進行拓撲排序的時候存在一個以上入度為0的點。

序列不存在會在圖中存在環的情況下出現。

于是，每輸入一組關系，進行一次拓撲排序，對此次拓撲排序的結果判斷并做出相應的選擇。

AC 代碼