You are given an undirected connected graph \(G\) with \(N\) nodes and \(M\) edges. Every node has a value \(A[i]\) assigned to it.

The value of a simple path between node \(u\) and \(v\) is as follows:

• The maximum absolute difference between the values of adjacent nodes present in the simple path.

Find the minimum possible path value of any simple paths between start and end nodes.

Input format

• The first line contains two space-separated integers \(N\) and \(M\) denoting the number of nodes and edges respectively.
• Next \(M\) lines contain two space-separated integers denoting edges.
• The next line contains \(N\) space-separated integers denoting node values.
• The next line contains two space-separated integers denoting the start ends.

Output format

Print the minimum possible path value of any simple path between start and end nodes.

Constraints