All Tracks Algorithms Graphs Depth First Search Problem

Sightseeing Walk
Tag(s):

DFS, Easy-Medium

Problem
Editorial
Analytics

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.

Constraints:

  • $$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$$.
SAMPLE INPUT
1
4 5
2 4 10 7
2 4
1 2
3 1
3 4
4 1
SAMPLE OUTPUT
5
Explanation

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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Clash '16

Notifications
View All Notifications