- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
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!
ورودی
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.
خروجی
In the only line of output display the $k$ digit number $x$ that is maximized.
Display $-1$ if no answer exists!
مثال
ورودی نمونه ۱
5 4 3
4 12 3 1 1
1 2
2 3
1 4
4 5
خروجی نمونه ۱
412
ورودی نمونه ۲
3 3 8
1 2 3
1 2
2 3
3 1
خروجی نمونه ۲
31231231
ورودی نمونه ۳
3 3 8
12 251 3200
1 2
2 3
3 1
خروجی نمونه ۳
-1
ارسال پاسخ برای این سؤال