This page is still under construction.

Parts of this page are still being built. What you see may change.

Sorting It All Out

Time limit1sMemory limit128 MB

Summary
Given up to n letter ordering constraints added one at a time, report the first point where a unique sorted order emerges or where the constraints contradict each other.
Level

Medium6 of 10

Topics
Graph, Topological sort, Implementation, Queue
Solved
No attempts yet

Problem

An ascending sorted sequence of distinct values orders the elements from smallest to largest using some form of a less-than operator. For example, the sorted sequence A, B, C, D implies A < B, B < C, and C < D. In this problem you are given a set of relations of the form A < B, and you must determine whether these relations specify a unique sorted order.

Input

The input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. The first value is the number of objects to sort, where 2≤n≤262 \le n \le 26. The objects to be sorted are the first n uppercase letters of the alphabet. The second value m is the number of relations of the form A < B given in this instance. The next m lines each contain one such relation, consisting of three characters: an uppercase letter, the character <, and a second uppercase letter. No letter lies outside the first n letters of the alphabet. A line with n = m = 0 marks the end of the input.

Output

For each problem instance, output a single line. This line must be exactly one of the following three:

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

Here xxx is the number of relations processed at the moment a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted ascending sequence. Relations are processed one at a time in order; as soon as the order becomes uniquely determined or a contradiction appears, the result is reported using the count of relations processed so far. If all relations are processed without determining a unique order and without any contradiction, the order cannot be determined.

Examples2

  1. Example 1

    Input
    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
    Expected output
    Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

  2. Example 2

    Input
    2 1
A<B
3 2
A<B
B<C
4 2
A<B
C<D
0 0
    Expected output
    Sorted sequence determined after 1 relations: AB.
Sorted sequence determined after 2 relations: ABC.
Sorted sequence cannot be determined.