## 题解 P1347 【排序】

#include<iostream>
#include<cstdio>
#include<algorithm>
#define II int
#define C char
#define R register
#define IL inline
#define I 30
using namespace std;

struct node {
II to,up;
}aa[I];

II _tot;

void add(R II x,R II y)
{
aa[++_tot].to=y;
}

II n,m,now;

IL II can()
{
for(R II i=1;i<=26;i++)
{
for(R II j=1;j<=26;j++)
{
for(R II k=1;k<=26;k++)
{
f[j][k]=max(f[j][k],f[j][i]&f[i][k]);
}
}
}

for(R II i=1;i<=26;i++) if(f[i][i]) return 0;
return 1;
}

IL II dfs(R II x,R II ka)
{
ans[ka]=x;
if(ka==n) return 1;
{
II g=aa[i].to;
if(dfs(g,ka+1)) return 1;
}
}
return 0;
}

int main()
{
//    freopen("1.in","r",stdin);

scanf("%d%d",&n,&m);
for(R II i=1;i<=m;i++)
{
R C a,b,z;
cin>>a>>z>>b;
R II ka1=a-'A'+1;
R II ka2=b-'A'+1;
f[ka1][ka2]=1;
in[ka2]++;

if(!can()) {
printf("Inconsistency found after %d relations.\n",i);
exit(0);
} else {
for(R II j=1;j<=26;j++)
{
if(!in[j]) {
if(dfs(j,1)) {
printf("Sorted sequence determined after %d relations: ",i);
for(R II k=1;k<=n;k++) printf("%c",ans[k]-1+'A');
cout<<'.'<<endl;
exit(0);
}
}
}
}
}

printf("Sorted sequence cannot be determined.\n");
exit(0);
}