All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Monk and Graph G
Tag(s):

Medium

Problem
Editorial
Analytics

Having some experience in the new world, Monk now wanted to meet some exciting people. He went to meet an undirected graph $$G$$ containing $$N$$ nodes (labeled from $$1$$ to $$N$$) and $$M$$ edges. But Graph $$G$$ likes people with some good intellectual level, so Graph $$G$$ first decided to check, whether Monk is a good choice to meet or not.
He asked Monk that considering the shortest path distance between nodes $$A$$ and $$B$$, Monk has to find a special node in this graph such that if we remove that node, the shortest path distance between A and B will increase.

Note that the node to be removed shouldn't be $$A$$ or $$B$$. If there doesn't exist any such node, print $$-1$$. If there are many such nodes, print the node having minimum label.

Note: If $$A$$ and $$B$$ aren't connected to each other, then the distance between them should be considered as infinity.

Monk really wants to meet Graph $$G$$. Please help him for the same.

INPUT:
First line will consists of two integers $$N$$ and $$M$$ denoting total number of nodes and total number of edges in this graph. Next $$M$$ lines will consists of two integers $$u$$ and $$v$$ denoting edge between nodes $$u$$ and $$v$$. Last line of input will consists of two nodes $$A$$ and $$B$$.

OUTPUT:
Output the label of node whose removal will increase the shortest path between $$A$$ and $$B$$. If there doesn't exists any such node, print $$-1$$. If there exists many such nodes, print the node having minimum label.

CONSTRAINTS:
2 ≤ N ≤ 105
N-1 ≤ M ≤ 106
1 ≤ A,B ≤ N
A != B

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

You can see that by removing 2, we can increase the shortest path distance between 1 and 5.

Time Limit: 1.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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Checkpoint - II)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications