AT_arc030_3 [ARC030C] 有向グラフ

有一个由 $n$ 个顶点和 $m$ 条边组成的有向图。$n$ 个顶点分别用 $1$ 到 $n$ 的不同整数编号。每个顶点上都写有一个从 `a` 到 `z` 的小写字母。 你可以从图中的任意一个顶点开始，并以任意顺序访问各个顶点，目的是恰好收集 $k$ 个字母。每个顶点可以被多次访问，如果该顶点上还有字母，可以在任意一次访问时收集该字母，但每个字母只能被收集一次。如果不需要，也可以选择不收集某些字母。 你觉得单纯收集字母太无聊了，所以想让收集到的 $k$ 个字母按收集顺序排列后，字典序最小。 请输出在满足上述条件下，按收集顺序排列的 $k$ 个字母的字典序最小的字符串。如果无法收集到恰好 $k$ 个字母，则输出 `-1`。

输入通过标准输入给出，格式如下： > $n$ $m$ $k$ > $c_1$ $c_2$ … $c_n$ > $a_1$ $b_1$ > $a_2$ $b_2$ > … > $a_m$ $b_m$ - 第 $1$ 行包含三个整数，分别表示图的顶点数 $n\ (1\leq n\leq 300)$、边数 $m\ (0\leq m\leq 1000)$ 和需要收集的字母数 $k\ (1\leq k\leq n)$。 - 第 $2$ 行包含 $n$ 个小写字母 $c_i$，第 $i$ 个字母表示顶点 $i$ 上写的字母，字母之间用空格分隔。 - 第 $3$ 行到第 $m+2$ 行，每行包含两个整数 $a_i$ 和 $b_i\ (1\leq a_i,b_i\leq n)$，表示第 $i$ 条有向边从 $a_i$ 指向 $b_i$。 - 图中不存在自环和重边，但可能存在反向边。图不一定连通。

输出一行，表示按字典序最小收集顺序得到的 $k$ 个字母组成的字符串。如果无法收集到恰好 $k$ 个字母，则输出 `-1`。最后请输出换行符。

### 样例解释 1 下图展示了该输入输出样例的情况。可以依次经过顶点 $4 \to 3 \to 1 \to 2$，在顶点 $4$ 收集 `a`，在顶点 $1$ 收集 `a`，在顶点 $2$ 收集 `b`，这样收集到的字母按顺序排列字典序最小。  ### 样例解释 4 三个顶点都是孤立的，无论从哪个顶点开始，都无法恰好收集到 $2$ 个字母。 由 ChatGPT 4.1 翻译