#AtCoder Regular Contest 030 有向グラフ(強連結成分分解&縮約グラフの構築、トポロジカルソート)

AtCoder Regular Contest 030 有向グラフ

強連結成分分解&縮約グラフの構築、トポロジカルソートのライブラリ用に。

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def SCC(graph, r_graph):
    n = len(graph)
    used = [0] * n
    group = [-1] * n
    order = []
    def dfs(u):
        used[u] = 1
        for v in graph[u]:
            if not used[v]:
                dfs(v)
        order.append(u)
    def rdfs(u, col):
        group[u] = col
        used[u] = 1
        for v in r_graph[u]:
            if not used[v]:
                rdfs(v, col)

    for i in range(n):
        if not used[i]:
            dfs(i)
    used = [0] * n
    label = 0
    for i in reversed(order):
        if not used[i]:
            rdfs(i, label)
            label += 1
    return label, group


n, m, k = LI()
word_list = LS()
G = [[] for _ in range(n)]
r_G = [[] for _ in range(n)]
for i in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    r_G[b - 1] += [a - 1]


group_num, group = SCC(G, r_G)
def contract(G, group, group_num):
    n = len(G)
    contracted_graph = [set() for _ in range(group_num)]
    for u in range(n):
        for v in G[u]:
            if group[u] == group[v]:
                continue
            contracted_graph[group[u]].add(group[v])
    return contracted_graph



each_group_words = [[] for _ in range(group_num)]
for i in range(n):
    each_group_words[group[i]] += [word_list[i]]

each_group_words = [''.join(sorted(words))[:k] for words in each_group_words]
contracted_graph = contract(G, group, group_num)


def topological_sort(graph):
    n = len(graph)
    in_degree = [0] * n
    for u in range(n):
        for v in contracted_graph[u]:
            in_degree[v] += 1
    topological_order = []
    que = deque()
    for i in range(n):
        if in_degree[i] == 0:
            que += [i]
    while que:
        u = que.pop()
        topological_order += [u]
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                que += [v]
    return topological_order


dp = [['~'] * (k + 1) for _ in range(group_num)]
for u in reversed(topological_sort(contracted_graph)):
    for left_len in range(k + 1):
        if len(each_group_words[u]) < left_len:
            continue
        left = each_group_words[u][:left_len]
        for right_len in range(k - left_len + 1):
            if contracted_graph[u]:
                right = min(dp[v][right_len] for v in contracted_graph[u] if len(dp[v][:right_len]) == right_len)
            else:
                right = ''
            if right == '~' or len(right) != right_len:
                break
            dp[u][left_len + right_len] = min(dp[u][left_len + right_len], left + right)

ans = min(dp[i][k] for i in range(group_num))
if ans == '~':
    print(-1)
else:
    print(ans)