All Tracks Algorithms Graphs Depth First Search Problem

Sightseeing Walk

DFS, Easy-Medium


Kevin wants to have a spectacular hiking tour over the mountains.

Now he needs to plan his route. Kevin knows N sightseeing points. Height of the i-th point equals \(H_i\). Also there are M lanes connecting these points. These lanes are designed in such a way that using the i-th lane Kevin can walk from point \(a_i\) to point \(b_i\). Note that he can't walk in the opposite direction using this lane but may walk using some other lane.

Kevin thinks that the path is the most spectacular if the height difference of his route is the largest. So he needs to choose \(start\) and \(finish\) points such that it is possible to reach \(finish\) from \(start\) and \(H_{finish} - H_{start}\) is maximized.

Your task is to help him and tell him the maximum possible \(H_{finish} - H_{start}\) .

Input format:

The first line of input will contain an integer T, denoting the number of test cases.
Each test case starts with 2 numbers N and M. Next line contains N numbers, \(H_i\). Next M lines contains 2 numbers \(a_i\) and \(b_i\)

Output format:

For every test case output one number - maximum height difference of the path.


  • \(1 \le T \le 10\)
  • \(0 \le H_i \le 10^9\)
  • \(1 \le a_i,b_i \le N\)
  • (20 points): \(1 \le N \le 1000, 1 \le M \le 2000\)
  • (80 points): \(1 \le N \le 10^5, 1 \le M \le 2 \cdot 10^5\).
4 5
2 4 10 7
2 4
1 2
3 1
3 4
4 1

Kevin's route is \(1 \to 2 \to 4\). Height difference equals \(H_4 - H_1 = 5\).

Time Limit: 3.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: 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, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

September Clash '16

View All Notifications