+ Time Limit : 1 second
+ Memory Limit : 256 megabytes
------------------------------
It is the well-known annual day *"Tavalbao"* , *Shengdebao*'s birthday!
In his birthday he has received gifts from all his friends and relatives. One particular present appeared the most interesting, A digraph (Directed Graph) which has $n$ vertices and $m$ directed edges. On vertex $i$ number $a_i$ is written. After his birthday party *Shengdebao* got bored and started traversing the graph. He decided to start from an arbitrary vertex $v$ and start traversing some edges in their directions. While doing so, he wanted to keep track of a number $x$. Initially number $x$ is equal to $a_v$ (the label written on the starting vertex) after passing an edge $a \to b$ he will write $a_b$ after the last digit of $x$.
For example if he starts from vertex $2$ with label $123$ and goes to vertex $1$ with label $78$ we will have $x = 12378$.
He intends to traverse over a walk (this walk can contain repeated edges or vertices) and write down number $x$ so that $x$ has exactly $k$ digits, since $k$ is his favorite number, and between all the available ways, $x$ should be **maximized**.
You're *Shengdebao*'s friend so give the guy a hand and help him!
# Input
In the first line numbers $n , m , k$ are given denoting the number of vertices , edges and *Shengdebao*'s favorite number in order.
Next line contains $n$ integers one after another, $i$th integer is equal to $a_i$. (the number written on vertex $i$)
Afterwards $m$ lines each consisting of two integers $u , v$ are given showing edge $u \to v$ exists in the graph.
$$ 1 \le u,v \le n $$
$$ n,m,k \le 1\ 000 $$
$$1 \le a_i \le 100\ 000 $$
The graph can contain loops or multiple edges.
# Output
In the only line of output display the $k$ digit number $x$ that is maximized.
Display $-1$ if no answer exists!
# Examples
## Sample input 1
```
5 4 3
4 12 3 1 1
1 2
2 3
1 4
4 5
```
## Sample output 1
```
412
```
## Sample input 2
```
3 3 8
1 2 3
1 2
2 3
3 1
```
## Sample output 2
```
31231231
```
## Sample input 3
```
3 3 8
12 251 3200
1 2
2 3
3 1
```
## Sample output 3
```
-1
```
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.