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 翻译