Competitions are not in fashion anymore.
What is fashionable now are *cooperative games*,
where the participants collaborate to achieve a common goal.
So, n friends get inspired by the chain game,
in which an array of people whisper
a message M in order from one extreme to the other one,
trying that M gets not corrupted on the way.
But, to make the game more fun,
some changes are made:

Let x be the initial transmitter of M,
and let y be the final receiver.
At each step of the game, the person u that just got M
(or x, if it is the first round)
must choose another person v and transmit M to him or her.
For every pair (u, v),
we know the probability p_{uv}
that the direct transmision of the message from u to v is correct.
That probability is independent of the round.
A corrupted message never gets recovered.
The game ends when M reaches y.

Playing optimally, what is the probability that M gets correctly transmitted from x to y?

Input

Input consists of several cases.
Every case begins with the number of friends n
and the number of probabilities p_{uv} that are strictly positive.
Follow m triplets u, v, p_{uv}, where u ≠ v.
Finally, we have x and y.
Assume 1 ≤ n ≤ 10^{4},
0 ≤ m ≤ 5n,
and that every pair of u and v appears at most once in the input.
Friends are numbered between 0 and n−1.

Output

For every case, print with five digits after the decimal point the maximum probability that the message correctly reaches y from x. If it is impossible, tell so.

Hint

The expected solution is based upon a fundamental graph algorithm.

Public test cases

**Input**

6 8 1 0 0.02478 3 4 0.49787 3 1 0.00335 0 5 0.06737 0 2 0.76787 5 1 0.00045 4 1 0.93533 2 3 0.18315 3 5 2 1 0 1 1 1 0 1 0 0 0 3 4 2 0 0.75008 0 2 0.00004 0 1 0.01831 1 2 0.00091 0 2

**Output**

0.00078 impossible 1.00000 0.00004

Information

- Author
- Enric Rodríguez
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++