[Solution] Toss a Coin to Your Graph... Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Toss a Coin to Your Graph... Codeforces Solution | Codeforces Problem Solution 2022

D. Toss a Coin to Your Graph...

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

One day Masha was walking in the park and found a graph under a tree... Surprised? Did you think that this problem would have some logical and reasoned story? No way! So, the problem...

Solution Click Below:-  CLICK HERE

Masha has an oriented graph which 𝑖$i$-th vertex contains some positive integer 𝑎𝑖$a_i$. Initially Masha can put a coin at some vertex. In one operation she can move a coin placed in some vertex 𝑢$u$ to any other vertex 𝑣$v$ such that there is an oriented edge 𝑢→𝑣$u\to v$ in the graph. Each time when the coin is placed in some vertex 𝑖$i$, Masha write down an integer 𝑎𝑖$a_i$ in her notebook (in particular, when Masha initially puts a coin at

AvtoBus Codeforces Solution

Stone Age Problem Codeforces Solution

Rooks Defenders Codeforces Solution

Toss a Coin to Your Graph... Codeforces Solution

Typical Party in Dorm Codeforces Solution

Formalism for Formalism Codeforces Solution 

 some vertex, she writes an integer written at this vertex in her notebook). Masha wants to make exactly 𝑘−1$k-1$ operations in such way that the maximum number written in her notebook is as small as possible.

Input

The first line contains three integers 𝑛$n$, 𝑚$m$ and 𝑘$k$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$, 0≤𝑚≤2⋅105$0\le m\le 2\cdot {10}^5$, 1≤𝑘≤1018$1\le k\le {10}^{18}$) — the number of vertices and edges in the graph, and the number of operation that Masha should make.

The second line contains 𝑛$n$ integers 𝑎𝑖$a_i$ (1≤𝑎𝑖≤109$1\le a_i\le {10}^9$) — the numbers written in graph vertices.

Each of the following 𝑚$m$ lines contains two integers 𝑢$u$ and 𝑣$v$ (1≤𝑢≠𝑣≤𝑛$1\le u\ne v\le n$) — it means that there is an edge 𝑢→𝑣$u\to v$ in the graph.

It's guaranteed that graph doesn't contain loops and multi-edges.

Output

Print one integer — the minimum value of the maximum number that Masha wrote in her notebook during optimal coin movements.

If Masha won't be able to perform 𝑘−1$k-1$ operations, print −1$-1$.

Join Now for Solution:-