Problem Description

There is a directed graph consisting of $ n $ vertices and $ m $ edges. The $ n $ vertices are numbered with distinct integers from $ 1 $ to $ n $. Each vertex has one alphabet from a to z written on it.

You want to start from any vertex and visit the vertices in any order to collect exactly $ k $ alphabets. You can visit a vertex multiple times, and if it has an alphabet, you can collect it at any visit, but once collected, the alphabet disappears. You do not have to collect it if you do not need it.

Since you think it would be boring to just collect them, you decided to collect these $ k $ alphabets in such an order that when arranged in the order of collection, they form the lexicographically smallest sequence.

Output the $ k $ alphabets collected in that order when such a collection method is performed. If there is no way to collect $ k $ alphabets, output -1.

Input Format

The input is given from the standard input in the following format:

$ n $ $ m $ $ k $ $ c_1 $ $ c_2 $ … $ c_n $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_{m} $ $ b_{m} $

• The first line contains the number of vertices $n\ (1\ ≦\ n\ ≦\ 300)$, the number of edges $m\ (0\ ≦\ m\ ≦\ 1000)$, and the number of alphabets you want to collect $k\ (1≦k≦n)$.
• The second line contains $ n $ alphabets $ c_i $ (lowercase alphabets from a to z) written on vertex $ i $, separated by spaces.
• From the third line to the $ m $th line, the $ i $th directed edge connects vertex numbers $ a_i $ and $b_i\ (1≦a_i,b_i≦n)$. This indicates that the $ i $th edge is a directed edge that can move from $ a_i $ to $ b_i $.
• The given graph does not have self-loops or multiple edges, but reverse edges may exist. It is not guaranteed to be connected.

Output Format

Output one line containing the $ k $ alphabets collected in lexicographically smallest order, in the order they were collected. If there is no way to collect $ k $ alphabets, output -1. Do not forget to end with a newline.

Sample Input and Output

Sample Input #1

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

Sample Output #1

aab

Sample Input #2

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

Sample Output #2

dabc

Sample Input #3

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

Sample Output #3

abc

Sample Input #4

3 0 2
a b c

Sample Output #4

-1

Notes/Hints

Sample Explanation 1

The diagram explaining this input/output example is as follows. Moving from vertex $ 4 $ → $ 3 $ → $ 1 $ → $ 2 $, you collect the a from vertex $ 4 $, the a from vertex $ 1 $, and the b from vertex $ 2 $ in order, resulting in the lexicographically smallest answer. 

Sample Explanation 4

The three vertices are isolated, and starting from any vertex, it is impossible to collect exactly two alphabets.

见题面 Input 部分

见题面 Output 部分