class Floyd:
    # max_node_num 表示所有点的编号最大值，点编号应该是1, 2, 3, .... max_node_num
    def __init__(self, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 返回所有点对的最短距离，用map表返回，key是(节点1，节点2)，值是节点之间的最短距离, 出现负权环或者无向图负边情况返回None
    # 稀疏图可以使用
    def getMinDis(self):
        pair2dis = {}
        all_nodes = set()

        for a, b, w in self.edges:
            all_nodes.add(a)
            all_nodes.add(b)

        for node1 in all_nodes:
            for node2 in all_nodes:
                pair2dis[(node1, node2)] = 0x7fffffff

        for a, b, w in self.edges:
            #pair2dis[(a, a)] = 0
            #pair2dis[(b, b)] = 0
            pair2dis[(a, b)] = w
            if not self.is_directed:
                pair2dis[(b, a)] = w

        for t in all_nodes:
            for node1 in all_nodes:
                for node2 in all_nodes:
                    new_dis = 0x7fffffff if pair2dis[(node1, t)] == 0x7fffffff or pair2dis[(t, node2)] == 0x7fffffff else pair2dis[(node1, t)] + pair2dis[(t, node2)]
                    pair2dis[(node1, node2)] = min(pair2dis[(node1, node2)], new_dis)

        return pair2dis

    # 返回点对的距离矩阵，稠密图使用
    def getMinDisMatrix(self):
        dis = [[0x7fffffff] * (self.max_node_num+1) for _ in range(self.max_node_num+1)]
        #for i in range(1, self.max_node_num+1):
        #    dis[i][i] = 0

        for a, b, w in self.edges:
            dis[a][b] = w
            if not self.is_directed:
                dis[b][a] = w

        for k in range(1, self.max_node_num+1):
            for i in range(1, self.max_node_num+1):
                for j in range(1, self.max_node_num+1):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

        return dis


while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break

    edges = []
    break_flag = False

    ss = []
    for i in range(m):
        ss.append(input())

    for iter_cnt, s in enumerate(ss):
        a, b = s[0], s[2]
        a, b = ord(a)-ord('A')+1, ord(b) - ord('A')+1
        edges.append((a,b,1))

        algo = Floyd(edges, is_directed=True, max_node_num=n)
        min_len = algo.getMinDisMatrix()      # 借用Floyd算法求传递闭包

        for i in range(1, n+1):
            if min_len[i][i] != 0x7fffffff:
                # 自己小于自己，发生矛盾
                print(f'Inconsistency found after {iter_cnt+1} relations.')
                break_flag = True
                break

        if break_flag:
            break

        known_cnt = 0
        for i in range(1, n+1):
            for j in range(1, n+1):
                if min_len[i][j] != 0x7fffffff:
                    known_cnt += 1


        if known_cnt == n*(n-1) // 2:
            lower_cnt = [0] * (n+1)     # 存储每一个数字中，比自己大的有多少个
            # 所有数对的大小关系都确定了，输出结果
            for i in range(1, n+1):
                for j in range(1, n+1):
                    if i == j:
                        continue

                    if min_len[i][j] != 0x7fffffff:
                        lower_cnt[i] += 1

            sort_arr = [None] * n
            for i in range(1, n+1):
                sort_arr[n-1-lower_cnt[i]] = chr(ord('A') + i-1)
            print(f'Sorted sequence determined after {iter_cnt+1} relations: {"".join(sort_arr)}.')
            break_flag = True

        if break_flag:
            break

    if not break_flag:
        print('Sorted sequence cannot be determined.')