SOLVE
LATER
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 ≤ 10^{5}
N-1 ≤ M ≤ 10^{6}
1 ≤ A,B ≤ N
A != B
You can see that by removing 2, we can increase the shortest path distance between 1 and 5.