#/usr/local/bin/python3

from collections import defaultdict

lines = []
keys = []
digits = []
orderings = defaultdict(set)

def recur_orderings(t, d, accum):
    if d not in t:
        return accum

    accum.update(t[d])

    for i in t[d]:
        recur_orderings(t, i, accum)

    return accum

with open('keylog.txt') as keylog_file:
    lines = keylog_file.readlines()

for l in lines:
    keys.append([int(i) for i in (l[0], l[1], l[2])])

for k in keys:
    orderings[k[0]].add(k[1])
    orderings[k[1]].add(k[2])

# digit -> set of all digits observed to follow after it
orderings_deep = {
    i:list(recur_orderings(orderings, i, set()))
    for i in orderings.keys()
}

# count of unique digits that follow a digit -> the digit
ordering_lengths = {
 len(v):k
 for k,v in orderings_deep.items()
}

# the digit that is observed to have no other digits follow it
leaders = set(orderings.keys())
followers = set()
followers.update(*orderings.values())
last = followers.difference(leaders).pop()

for k in reversed(sorted(ordering_lengths.keys())):
    digits.append(ordering_lengths[k])

digits.append(last)

# verify that the digits deduced satisfies the observed keys
run_test = True
if run_test:
    idx = {v:k for k,v in enumerate(digits)}
    for k1, k2, k3 in keys:
        assert(idx[k1] < idx[k2] < idx[k3])

print(*digits, sep='')