Asia Hong Kong Online Preliminary

Start

2016-09-10 05:00 UTC

Asia Hong Kong Online Preliminary

End

2016-09-10 10:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -802 days 13:45:26

Time elapsed

5:30:00

Time remaining

0:00:00

Problem H
Let's Meet

MTR (subway) stations are common meetup locations in Hong Kong. Alice and Bob are going to meet up at one of the MTR stations. They each show up at the meeting spot in one of the stations right at noon, without remembering which station they plan to meet at. Having poor cellphone connection at the stations, they fail to contact the other person. Fortunately, they have agreed to look for each other with the following strategy.

Each station has a unique designated meeting spot. Every minute starting from noon, Alice and Bob look for the other person at the meeting spot of their current stations. If they happen to be at the same station, they can finally meet up. Otherwise, they each takes a train to reach a neighbouring station, uniformly at random from among the neighbouring stations. Upon arrival, they look for the other person at the meeting spot of their current stations. If they still cannot find each other, each of them again takes a train to reach a neighbouring station, uniformly at random. This process goes on until they are at (the meeting spot of) the same station at the same time.

Trains move very fast, so Alice and Bob will not see each other while on trains running in opposite directions. Suppose it takes exactly one minute to get from the meeting spot of one station to that of a neighbouring station. What is the expected time they will meet?

Input

The first line of input contains two integers $n$ and $m$. $n$ is the number of MTR stations ($1 \leq n \leq 20$, $0 \leq m \leq n(n-1)/2$) and $m$ is the number of pairs of stations that are neighbours.

Each of the following $m$ lines contains two distinct integers, $u$ and $v$ ($0 \leq u, v < n$, $u \neq v$), indicating that stations $u$ and $v$ are neighbours. Every unordered pair of neighbours $(u,v)$ will appear at most once in the input.

The last line consists of two integers $s$ and $t$ ($0 \leq s, t < n$), denoting the initial stations of Alice and Bob, respectively.

Output

If Alice and Bob will never meet, output “never meet” without the quotes. Otherwise, output a real number indicating the expected time (in minutes past noon) they will meet at the meeting spot of a certain station. Any solution with a relative or absolute error of $10^{-6}$ will be accepted.

Sample Input 1 Sample Output 1
3 2
0 1
1 2
0 2
1
Sample Input 2 Sample Output 2
4 2
0 1
2 3
0 3
never meet