← 返回题目列表

AtCoder · arc030_3

C. 有向图

中文机器翻译题面 查看原题

問題文

n 顶点和 m 我有一个由书本边缘组成的有向图。n 顶点是 它们用不同的整数 1 假设一直下雨,直到 n 进行编号。 在每个顶点,a 假设一直下雨,直到 z 字母表是 1 已写入。

您可以通过从任何顶点开始并以任何顺序访问每个顶点来运行此图,只需 我想收集 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 ≦ n ≦ 300) 和一个表示边数的整数 m (0 ≦ m ≦ 1000) 和一个代表您要收集的字母数量的整数 k (1≦k≦n) 。
  • 2 行包含顶点 字母写在 i 写在上面的字母 c_i( a 假设一直下雨,直到 z 小写字母)是 给出 n ,用空格分隔。
  • 3 行开始 m 行、图 第 i 条有向边连接的顶点数 给出 a_i 和 在 b_i (1≦a_i,b_i≦n) 。这是i 第边是 它表示可以移动到a_i 假设一直下雨,直到 b_i 的有向边。
  • 尽管给定图中不存在自边或多重边,但可能存在相对边。此外,不保证串联。 在

出力

1 行中,收集的数据是按字典顺序排列的最小值。 按照收集的顺序输出 k 字母表。 输出k 字母表,那么 输出-1 。不要忘记最后的换行符。


入力例1

4 4 3
a b b a
1 2
2 3
3 1
4 3

出力例1

aab

解释该输入/输出示例的图如下。顶点 在移动 4 → 3 → 1 → 2 的过程中,顶点 4 的 a,頂点 1 的 a,以及顶点 通过按顺序收集 2 的 b ,您将得到按字典顺序排列的最小答案。


入力例2

5 4 4
d a b c a
1 2
2 3
3 4
2 5

出力例2

dabc

入力例3

5 4 3
d a b c a
1 2
2 3
3 4
2 5

出力例3

abc

入力例4

3 0 2
a b c

出力例4

-1

3 两个顶点是孤立的,无论从哪个顶点开始,都准确 无法收集 2 字母表。