SPOJ Brasil

Embora não seja uma modalidade muito popular no Brasil, as corridas de dragsters atraem multidões nos EUA. Os fãs gostam de ver os carros velozes correndo a velocidades de até 400 km/h, mesmo que só por alguns segundos. Muitos competidores são mecânicos amadores que apenas incluiram foguetes e outros artefatos para criarem carros ultra velozes. As competições de dragsters são disputadas em torneios de eliminação, onde cada disputa consiste de dois competidores correndo lado a lado e somente um deles sendo declarado o vencedor (o que chegar primeiro, claro). Os vencedores são então rearranjados em novas partidas, até que no final somente um competidor seja declarado o campeão.

Rubens é um piloto experiente, com carreira em diversas categorias, inclusive a Fórmula 1. Entretanto, após enfrentar alguns contratempos, resolveu dedicar-se a competições de dragsters.

Aproveitando-se da larga experiência que ganhou durante a Fórmula 1, ele consegue, observando os competidores, dizer qual a probabilidade de cada um dos competidores envolvidos ser o vencedor de uma dada disputa.

Embora Rubens seja bom piloto, não é muito bom em matemática nem em programação, e pediu a sua ajuda para, dadas as probabilidades calculadas por Rubens para a disputa entre cada par de pilotos, e a descrição das corridas do torneio, determinar a probabilidade que ele tem de vencer o torneio.

Entrada

A entrada é composta de vários casos de teste. A primeira linha de um caso de teste contém um inteiro N indicando o número de competidores do torneio (2≤N≤300). Na descrição do torneio, os competidores são identificados por inteiros de 1 a N, e as corridas são identificadas por inteiros de N + 1 a 2 × N - 1. Rubens é sempre identificado pelo número 1. As N linhas seguintes descrevem a matriz M de probabilidades calculada por Rubens. A linha i contém N números reais M[i, j] separados por espaços (0≤M[i, j]≤1, para 1≤i≤N e 1≤j≤N). Cada elemento M[i, j] da matriz indica a probabilidade de o competidor i vencer o confronto com o competidor j (0.001≤M[i, j]≤0.999 e M[i, j] + M[j, i] = 1 para i≠j , e M[i, j] =0 para i = j). As probabilidades serão sempre dadas com três casas decimais de precisão. Cada uma das N - 1 linhas seguintes contém dois inteiros A, B descrevendo uma corrida, sendo que A e B representam identificadores de competidores ou de corridas (1≤A≤2 x N - 1 e 1≤B≤2 x N - 1). Note que a primeira dessas linhas descreve a corrida identificada por N +1, a segunda linha descreve a corrida identificada por N +2 e assim por diante. Quando um identificador de corrida k aparece na entrada como A, isto significa que o competidor que venceu a corrida k é quem disputará a corrida contra B. Da mesma forma, quando um identificador de corrida k aparece na entrada como B, isto significa que o competidor que venceu a corrida k é quem disputará a corrida contra A.

O final da entrada é indicado por uma linha que contém apenas um número zero.

Os dados devem ser lidos da entrada padrão.

Saída

Para cada caso de teste da entrada seu programa deve imprimir uma única linha, contendo um número real, escrito com precisão de seis casas decimais, indicando a probabilidade de Rubens vencer o torneio.

O resultado de seu programa deve ser escrito na saída padrão.

Exemplo

Entrada:
4
0.000 0.500 0.400 0.400
0.500 0.000 0.500 0.500
0.600 0.500 0.000 0.600
0.600 0.500 0.400 0.000
1 2
3 4
5 6
5
0.000 0.500 0.600 0.600 0.001
0.500 0.000 0.500 0.500 0.500
0.400 0.500 0.000 0.500 0.500
0.400 0.500 0.500 0.000 0.500
0.999 0.500 0.500 0.500 0.000
3 8
9 6
4 5
1 2
0

Saída:
0.200000
0.225125