Dragster

Dragster racing is not a popular sport in Brazil, but in the United States it draws big crowds. Fans come to watch the cars run at speeds of up to 400 km/h, even when a single run lasts only a few seconds. Many of the competitors are amateur mechanics who bolted rockets and other contraptions onto a chassis to build an extremely fast car.

A dragster competition runs as an elimination tournament. Every race puts two competitors side by side and exactly one of them is the winner, the one who finishes first. The winners are paired into new races until a single competitor is left as the champion.

Rubens is an experienced driver who raced in several categories, Formula 1 among them. After a run of setbacks he decided to devote himself to dragsters.

Because of the experience he built up in Formula 1, Rubens can watch the competitors and state, for any two of them, the probability that each one wins a race between the two.

Rubens drives well but he is weak at mathematics and at programming, so he asked you for help. You are given the probabilities Rubens computed for every pair of drivers and the description of the races in the tournament. Determine the probability that Rubens wins the tournament.

The input holds several test cases.

The first line of a test case has one integer $N$, the number of competitors in the tournament ($2 \le N \le 300$). Competitors are identified by the integers $1$ to $N$ and races are identified by the integers $N + 1$ to $2N - 1$. Rubens is always competitor $1$.

The next $N$ lines describe the probability matrix $M$ that Rubens computed. Line $i$ has $N$ real numbers $M_{i,j}$ separated by single spaces. Each element $M_{i,j}$ is the probability that competitor $i$ beats competitor $j$. For $i \ne j$, $0.001 \le M_{i,j} \le 0.999$ and $M_{i,j} + M_{j,i} = 1$; for $i = j$, $M_{i,j} = 0$. Every probability comes with exactly three decimal places.

Each of the next $N - 1$ lines has two integers $A$ and $B$ describing one race ($1 \le A \le 2N - 1$ and $1 \le B \le 2N - 1$). The first of these lines describes the race identified by $N + 1$, the second line describes the race identified by $N + 2$, and so on. $A$ and $B$ are identifiers of competitors or of races. When a race identifier $k$ appears as $A$, the winner of race $k$ is the one who runs this race against $B$; when $k$ appears as $B$, the winner of race $k$ runs against $A$.

Each competitor and each race is used at most once as a participant of another race, so exactly one race identifier never appears as $A$ or $B$. That race is the final and its winner is the champion.

The end of the input is a line that holds a single zero.

For each test case print one line with a real number, written with exactly six decimal places, giving the probability that Rubens wins the tournament.