Time Limit: 1000MS Memory Limit: 10000KB 64bit IO Format: %lld & %llu

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

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


Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

AC代码：
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n, m;
struct node
{
int v, next;
}e;
int k, head;
int in, ans, cnt;
queue <int> q;
void adde(int u, int v)
{
e[k].v = v;
e[k].next = head[u];
head[u] = k++;
in[v]++;
}
int topsort()
{
while (!q.empty())
q.pop();
for (int i = 0; i < n; i++)
if (!in[i])
q.push(i);
cnt = 0;
int in2;
memcpy(in2, in, sizeof(in));
bool flag = 0;
while (!q.empty())
{
if (q.size() > 1)
flag = 1;
int u = q.front();
q.pop();
ans[cnt++] = u;
for (int i = head[u]; i != -1; i = e[i].next)
{
int v = e[i].v;
if (!(--in2[v]))
q.push(v);
}
}
if (cnt != n)//环
return 0;
if (flag)//不确定
return 1;
return 2;//唯一
}
int main()
{
while (scanf("%d %d\n", &n, &m) && n && m)
{
char a, b;
k = 1;
memset(head, -1, sizeof(head));
memset(in, 0, sizeof(in));
bool ok = 0;
for (int i = 1; i <= m; i++)
{
scanf("%c<%c\n", &a, &b);
if (!ok)
{
adde(a - 'A', b - 'A');
int rc = topsort();
if (rc == 2)
{
printf("Sorted sequence determined after %d relations: ", i);
for (int j = 0; j < cnt; j++)
printf("%c", ans[j] + 'A');
printf(".\n");
ok = 1;
}
else if (rc == 0)
{
printf("Inconsistency found after %d relations.\n", i);
ok = 1;
}
}
}
if (!ok)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}