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, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Checkpoint - II)

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Basic Programming > Implementation
• Basic Programming > Implementation
• Algorithms > Searching
• Data Structures > Disjoint Data Structures