Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

F. Failing Factory
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The gigafactory for your new range of Battery-Assisted Postal Cars is finally up and running. This manufacturing plant is a highly complex facility, consisting of many individual steps, where the parts of each car are milled, stamped, welded, soldered, screwed, glued, assembled, tested, detailed, layered, painted, and cleaned. Every step is optimized to the tiniest detail, making them very complicated.

As you are preparing for a visit from your main investor, alarm bells start going off. One of the steps failed, causing a cascade of failures across the factory! After hurriedly resolving the failures, panic creeps up to you: what if a failure happens during the visit of the investor?

Currently, all processes in the factory are working, but your engineers determined that each of them has some independent probability of failing before the visit. As the visit is soon, there will be no time for any repairs, and as soon as a step fails, this will quickly halt all dependent steps as well.

Thus, you decide to show only a single processing step of your factory, and specifically, the one with the smallest probability of failing. As an example, consider the second sample case. The probability that step $$$1$$$ fails is $$$0.72$$$, but step $$$2$$$ is slightly more stable with a failure probability of $$$0.6$$$. Thus, you show step $$$2$$$ to your investor, with a probability of $$$0.4$$$ that it will not fail.

Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 10^5$$$), the number of steps and the number of dependencies between steps.
  • One line with $$$n$$$ floating point numbers $$$p$$$ ($$$0 \leq p \leq 1$$$), the individual failure probability of each step. Each probability is given in decimal form with exactly three digits after the decimal point. When a floating-point number is written in decimal form, it is not in scientific notation.
  • $$$m$$$ lines, each with two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$), indicating that step $$$a$$$ depends on step $$$b$$$: failure of step $$$b$$$ will cause failure of step $$$a$$$. A direct dependency of one step on another occurs at most once. Cyclic dependencies are allowed.
Output

For the step with the smallest probability of failing, output the probability that it will not fail.

Your answer should have an absolute error of at most $$$10^{-200}$$$ or a relative error of at most $$$10^{-6}$$$.

Examples
Input
2 2
0.600 0.300
1 2
2 1
Output
0.27999999999999999997
Input
2 1
0.300 0.600
1 2
Output
0.39999999999999999998
Input
4 3
0.999 0.994 0.998 0.996
1 2
2 3
3 4
Output
0.0039999999999999999748
Input
4 4
0.999 0.994 0.998 0.996
1 2
2 3
3 4
4 1
Output
4.8000000000000000518e-11