드래그스터

드래그스터 경기는 브라질에서는 인기 종목이 아니지만 미국에서는 많은 관중을 끌어모은다. 팬은 시속 400km까지 내달리는 차를 보러 오고, 한 번의 주행이 몇 초에 그쳐도 개의치 않는다. 참가자 중에는 차체에 로켓과 온갖 장치를 얹어 초고속 차를 만든 아마추어 정비사가 많다.

드래그스터 대회는 토너먼트로 치른다. 한 경주에서는 참가자 두 명이 나란히 달리고, 먼저 도착한 한 명만 승자가 된다. 승자끼리 다시 짝을 지어 경주를 이어가고 마지막에 한 명이 챔피언으로 남는다.

루벤스는 포뮬러 1을 포함해 여러 종목을 뛴 노련한 드라이버다. 몇 차례 어려움을 겪은 뒤 드래그스터에 전념하기로 했다.

포뮬러 1에서 쌓은 경험이 있어서 루벤스는 참가자를 지켜보기만 해도 두 사람이 맞붙었을 때 각자가 이길 확률을 말할 수 있다.

루벤스는 운전은 잘하지만 수학과 프로그래밍에는 약해서 당신에게 도움을 청했다. 루벤스가 계산한 모든 참가자 쌍의 확률과 토너먼트 경주 구성이 주어진다. 루벤스가 우승할 확률을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 대회 참가자 수를 나타내는 정수 $N$이 주어진다 ($2 \le N \le 300$). 참가자는 $1$부터 $N$까지의 정수로, 경주는 $N + 1$부터 $2N - 1$까지의 정수로 구분한다. 루벤스는 항상 참가자 $1$번이다.

이어지는 $N$개의 줄에는 루벤스가 계산한 확률 행렬 $M$이 주어진다. $i$번째 줄에는 실수 $M_{i,j}$가 $N$개, 공백 하나로 구분되어 주어진다. $M_{i,j}$는 참가자 $i$가 참가자 $j$와 맞붙어 이길 확률이다. $i \ne j$이면 $0.001 \le M_{i,j} \le 0.999$이고 $M_{i,j} + M_{j,i} = 1$이며, $i = j$이면 $M_{i,j} = 0$이다. 모든 확률은 소수점 아래 세 자리로 주어진다.

다음 $N - 1$개의 줄에는 경주 하나를 설명하는 정수 $A$와 $B$가 주어진다 ($1 \le A \le 2N - 1$, $1 \le B \le 2N - 1$). 첫 줄은 번호가 $N + 1$인 경주를, 둘째 줄은 번호가 $N + 2$인 경주를 설명하고 그다음도 같은 방식이다. $A$와 $B$는 참가자 번호이거나 경주 번호다. 경주 번호 $k$가 $A$ 자리에 오면 경주 $k$의 승자가 $B$와 맞붙고, $k$가 $B$ 자리에 오면 경주 $k$의 승자가 $A$와 맞붙는다.

참가자와 경주는 다른 경주의 출전자로 최대 한 번만 쓰이므로, $A$나 $B$ 자리에 한 번도 나오지 않는 경주 번호가 정확히 하나 있다. 그 경주가 결승이고 그 승자가 챔피언이다.

입력의 끝에는 $0$ 하나만 있는 줄이 주어진다.

각 테스트 케이스마다 루벤스가 우승할 확률을 소수점 아래 여섯 자리로 한 줄에 출력한다.