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 nn vertices and mm directed edges. On vertex ii number aia_i is written. After his birthday party Shengdebao got bored and started traversing the graph. He decided to start from an arbitrary vertex vv and start traversing some edges in their directions. While doing so, he wanted to keep track of a number xx. Initially number xx is equal to ava_v (the label written on the starting vertex) after passing an edge aba \to b he will write aba_b after the last digit of xx.

For example if he starts from vertex 22 with label 123123 and goes to vertex 11 with label 7878 we will have x=12378x = 12378.

He intends to traverse over a walk (this walk can contain repeated edges or vertices) and write down number xx so that xx has exactly kk digits, since kk is his favorite number, and between all the available ways, xx 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,kn , m , k are given denoting the number of vertices , edges and Shengdebao's favorite number in order.

Next line contains nn integers one after another, iith integer is equal to aia_i. (the number written on vertex ii)

Afterwards mm lines each consisting of two integers u,vu , v are given showing edge uvu \to v exists in the graph.

1u,vn 1 \le u,v \le n n,m,k1 000 n,m,k \le 1\ 000 1ai100 0001 \le a_i \le 100\ 000

The graph can contain loops or multiple edges.

Output🔗

In the only line of output display the kk digit number xx that is maximized.

Display 1-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
Plain text

Sample output 1🔗

412
Plain text

Sample input 2🔗

3 3 8
1 2 3
1 2
2 3
3 1
Plain text

Sample output 2🔗

31231231
Plain text

Sample input 3🔗

3 3 8
12 251 3200
1 2
2 3
3 1
Plain text

Sample output 3🔗

-1
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.