+ 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 ```

Tavalbao

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🔗

Sample output 1🔗

Sample input 2🔗

Sample output 2🔗

31231231

Sample input 3🔗

3 3 8
12 251 3200
1 2
2 3
3 1

Sample output 3🔗

-1