ECOO '19 R1 P2 - L-Systems Go

for _ in range(10):
    r, t, a = input().split()
    r = int(r)
    t = int(t)

    # Key - C
    # Value - S
    rules = dict()

    length = 0
    freq = dict()

    for c in a:
        freq[c] = freq.get(c, 0) + 1

    for i in range(r):
        # Record all the rules and their lengths in
        # the rules dictionary.
        c, s = input().split()
        rules[c] = s

    for i in range(t):
        # We only need to care about the first and last
        # letters for each iteration. a[-1] returns the
        # last letter.
        if len(a) == 1:
            a = rules[a]
        else:
            a = rules[a[0]][0] + rules[a[-1]][-1]

        for c, count in list(freq.items()):
            freq[c] -= count
            for x in rules[c]:
                freq[x] = freq.get(x, 0) + count

    print(a[0] + a[-1], sum(freq.values()))