SOLVE

LATER

Sightseeing Walk

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$$.

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++,
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,
Visual Basic

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"ddccf20": "/pagelets/suggested-problems/algorithm/sightseeing-walk-september-clash/", "d092951": "/pagelets/problem-author-tester/algorithm/sightseeing-walk-september-clash/", "b9f27e7": "/pagelets/show-submission/algorithm/sightseeing-walk-september-clash/", "cc4fe10": "/pagelets/recommended-problems/algorithm/sightseeing-walk-september-clash/", "d3c7e02": "/pagelets/problems-hint/algorithm/sightseeing-walk-september-clash/"}

realtime.hackerearth.com

80

bc8f73b5eb65b6b111b6e12122b5fc8cc8469c5a

58a29e5cae2309f04b28

/realtime/pusher/auth/