Lost in a city
Tag(s):

## Algorithms, Dijkstra, Easy-Medium, Graphs, Shortest Path Algorithms

Problem
Editorial
Analytics

A country consists of $n$ cities and $m$ one-way roads. There is a central city with number $s$. Each city sells a particular sweet (city $i$ sells sweets of value $v[i]$).

You are required to go to city $d$. If you are currently in city $x$, then you can randomly select and move to one of the cities that is directly reachable from $x$ through a single road. You can perform this technique until you reach city $d$. You must stop once you reach the destination city.

You can buy sweets only once on your way. Determine the highest value $p$ such that you can take home a sweet whose value is at least $p$ independent of the path that you take. Print the value of $p$ for each destination city $d$ from $1$ to $n$

Note

• It is guaranteed that all the cities are reachable from the central city.
• You can not select a road that does not lead to the destination.
• There are multiple test cases in a single input file.

Input format

• First line: An integer $t$ denoting the number of test cases
• For each test case:
• First line: Three integers $n$$m$, and $s$
• Next line: $n$ integers denoting the value of a sweet that is sold in each city
• Next $m$ lines: Two integers $u$ and $v$ denoting a directed road from city $u$ to $v$

Output format

For each test case, print $n$ space-separated integers denoting the answer to each destination city.

Constraints

$1 \leq t \leq 3$

$1\le n,u,v,s\le10^5$

$1\le m\le2*10^5$

$1\le v[i]\le10^6$

SAMPLE INPUT
2
3 4 1
3 4 5
1 2
1 3
2 3
3 2
4 5 2
6 3 2 5
2 1
2 4
1 3
4 3
3 1
SAMPLE OUTPUT
3 4 5
6 3 5 5

Explanation

In the second testcase:

There is only one path for reaching city 1, and he will buy sweets of value 6 in city 1. There is also only one path for reaching city 4 and he will buy sweets of value 5 from city 4. There are two paths 2->4->3 and 2->1->3 for reaching city 3. In the first path he can buy sweets of value 5 from city 4 and in the second path he can buy sweets of value 6 from city 1. So he can take sweets of value at least 5 if the destination city is 3.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

July Circuits '19

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Math > Combinatorics
• Math > Probablity
• Data Structures > Disjoint Data Structures
• Math > Linear Algebra

?