Problem F - USTC Online Judge

Rank

Problem F

Crazy Biscuits

Time Limit: 1000ms
Memory Limit: 65536kb

Description

Dango baked some biscuits in the evening. The biscuits lied down in the box peacefully until she went to bed.

Each biscuit had a little letter printed by chocolate on it. When the night came, metal box shimmered in the moonlight and all the biscuits woke up. After a while, they found out that all of them were wearing the little letter coat. They decided to determine their relationship such as Biscuit D > Biscuit A> Biscuit N> Biscuit G> Biscuit O, because they were so bored.

The biscuits themselves didn’t have a judge or something like that, so they woke up Mr. Box and let him be their judge. Mr. Box was too sleepy, so he made a hard decision that he would like to talk in his sleep. “A<B, A<C, B<C……” he murmured. Because Mr. Box was talking in his sleep, there may be inconsistency between his words.

Now, Dear Desk, it is your time to determine whether a sorted order has been specified or not.

Input

First line contains one integer T. It stands for how many test cases you should process.
Each data set starts with a line containing two positive integers n(2 <= n <= 26) and m. N is the number of kind of crazy biscuit. M stands for the number of relations Mr. Box murmured. The biscuit to be sorted will be the first n characters of the uppercase alphabet. Next m lines are what Mr. Box murmured, the relations are in the form of an uppercase letter, the character "<" and another uppercase letter. (All the letters will be in the range of the first n letters of the alphabet.)

Output

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

Case xx: Sorted sequence determined after xxx murmurs: yyy...y.
Case xx: Inconsistency found after xxx murmur.
(xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found. yyy...y is the sorted, ascending sequence. Notice: After printing sorted sequence or finding inconsistency, read the remaining input and ignore them.)
Case xx: Mr.Box, please say something more.
(If Sorted sequence cannot be determined, print that.)

Sample Input

3
3 1
A<B
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A

Sample Output

Case 1: Mr.Box, please say something more.
Case 2: Sorted sequence determined after 4 murmurs: ABCD.
Case 3: Inconsistency found after 2 murmur.

Source

yislin@USTC

[Submit|Discuss|Add to bookmark]