Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Set the Meeting

By shajia · Limits 1s, 512 MB

Three colleagues Motu, Biscuit and Ramjan are in Sundarbans now. They are on a mission to protect the environment. In each day, they have to discuss their plans together. But they have a lot to work on within a short period of time. Hence, they need to reduce the duration of their traveling. So they decided to set their everyday meeting in such a place that the summation of the duration for each of the friend’s traveling time is minimized.

A region of Sundarbans is selected for their work. On that region, they set some connected workstations. Hence, it is possible to visit all the workstations if someone starts from any particular workstation. It is also guaranteed that between each pair of workstations, there exists exactly one path. The colleagues are staying in three different stations that are suitable for their work. In order to meet, they have to choose a workstation considering the requirements described above. The traveling time between any two directly connected workstations are equal. As they are running out of time, help them to choose the workstation that will be convenient for them.

Input

The first line of input contains two space separated integers NN (3N105 3 \leq N \leq 10^5 ) and EE that denotes the number of workstations and the number of connections between two workstations.

In each of the next EE lines, there will be two integers uu and vv (1u,vN1 \leq u, v \leq N) that denotes a direct connection between two distinct workstations.

Then in the next line, there will be three space separated integers aa, bb and cc (1a,b,cN1 \leq a,b,c \leq N) that denotes the current workstation of Motu, Biscuit and Ramjan respectively. You can safely assume that the current workstations of each of the colleagues are distinct from each other.

Output

For each input, output the node that is optimal for all of the colleagues. If there are more than one workstation that fulfills the requirement, print the one that has the lower number.

Sample

InputOutput
4 3
1 2
1 3
1 4
2 3 4
1

Discussion

Statistics


71% Solution Ratio

farhan132Earliest, 1M ago

rohijulislamFastest, 0.0s

MR.Jukerburg11Lightest, 6.2 MB

sh2018331053Shortest, 688B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.