Octopus

The octopus is one of the few animals seen using tools on purpose to get a job done. A well known video shows an octopus carrying two coconut half shells across the sea floor and hiding inside them when it feels threatened.

Hiding tools differ in quality. When portable hiding tools are scattered over the sea floor, a small detour to pick up a better one raises the chance of not being eaten. Write a program that plans the route with the highest survival probability.

You are given $n$ locations on the sea floor and the passages between them. Each location holds a predator, or a hiding tool, or neither. A predator has a detection skill $p$, a real number between $0$ and $1$. A hiding tool has a protective value $h$, a real number between $0$ and $1$. When an octopus using a tool of protective value $h$ stays at a location with a predator of skill $p$, that predator eats it with probability $\max(0, p - h)$.

The octopus starts at location $s$ carrying nothing, so its protective value starts at $0$. It travels along passages and has to reach location $t$. The rules are as follows.

• Whenever the octopus stays at a location, it faces the predator check of that location. The check also happens at the start location $s$ and at the target location $t$, and it happens again every time the octopus passes the same location again.
• On reaching a location with a hiding tool, the octopus can pick that tool up. It keeps every tool it picks up, and when it holds several tools it uses the one with the largest protective value.
• The octopus can travel over the same passage and through the same location any number of times.

The checks are independent of each other. Find the largest probability that the octopus starts at $s$ and reaches $t$ alive.

The first line contains the number of data sets $K$, with $K \ge 1$. Then come $K$ data sets in the following form.

The first line of a data set contains four integers $n$, $m$, $s$, $t$. Here $1 \le n \le 200$ is the number of locations, $0 \le m \le n^2$ is the number of passages, and $1 \le s, t \le n$ are the start and target locations.

The next line contains $n$ real numbers $z_1, z_2, \ldots, z_n$, each between $-1$ and $1$. If $z_i < 0$, location $i$ holds a hiding tool of protective value $-z_i$. If $z_i > 0$, location $i$ holds a predator of detection skill $z_i$. If $z_i = 0$, location $i$ holds neither a predator nor a hiding tool.

Each of the next $m$ lines describes one passage. Line $j$ contains two integers $p_j$, $q_j$ with $1 \le p_j < q_j \le n$, meaning the octopus can travel directly from location $p_j$ to $q_j$ and from $q_j$ to $p_j$. The same passage can appear more than once. There is always a way to get from $s$ to $t$.

For each data set, first print Data Set x: on a line of its own, where $x$ is the number of the data set counting from $1$. On the next line print the largest probability that the octopus reaches location $t$ alive, rounded to four decimal places. Print exactly four digits after the decimal point.

Print one blank line after each data set.