문어

문어는 도구를 써서 일을 해내는 모습이 관찰된 몇 안 되는 동물이다. 코코넛 껍데기 두 쪽을 바닥에서 들고 다니다가 위험을 느끼면 그 안으로 숨는 문어의 영상이 널리 알려져 있다.

은신 도구는 성능이 서로 다르다. 바다 바닥 여러 곳에 들고 다닐 수 있는 은신 도구가 흩어져 있다면, 조금 돌아가서 더 좋은 도구를 챙긴 다음 목적지로 향하는 편이 잡아먹히지 않을 확률을 높인다. 살아남을 확률이 가장 높은 경로를 계획하는 프로그램을 작성하라.

바다 바닥의 위치 $n$개와 위치 사이를 잇는 통로가 주어진다. 각 위치에는 포식자가 있거나 은신 도구가 있거나 둘 다 없다. 포식자의 탐지 능력은 $0$과 $1$ 사이의 실수 $p$이고, 은신 도구의 보호력은 $0$과 $1$ 사이의 실수 $h$이다. 보호력 $h$인 도구를 쓰는 문어가 탐지 능력 $p$인 포식자가 있는 위치에 머무르면, 포식자는 확률 $\max(0, p - h)$로 문어를 잡아먹는다.

문어는 출발 위치 $s$에서 아무 도구도 없이 출발하므로 처음 보호력은 $0$이다. 통로를 따라 이동해 목표 위치 $t$에 도달해야 하며, 규칙은 다음과 같다.

• 문어가 어떤 위치에 머무르면 그 위치의 포식자 판정을 받는다. 출발 위치 $s$와 목표 위치 $t$에서도 판정을 받고, 같은 위치를 다시 지나면 판정을 다시 받는다.
• 은신 도구가 있는 위치에 도달하면 그 도구를 집을 수 있다. 집은 도구는 계속 가지고 다니고, 여러 개를 가지고 있으면 그중 보호력이 가장 큰 도구를 쓴다.
• 같은 통로와 같은 위치는 몇 번이든 다시 지날 수 있다.

각 판정은 서로 독립이다. 문어가 $s$에서 출발해 $t$까지 살아서 도달할 확률의 최댓값을 구하라.

첫 줄에 데이터 세트의 개수 $K$가 주어진다. $K \ge 1$이다. 이어서 데이터 세트 $K$개가 다음 형식으로 주어진다.

데이터 세트의 첫 줄에는 정수 네 개 $n$, $m$, $s$, $t$가 주어진다. $1 \le n \le 200$은 위치의 개수, $0 \le m \le n^2$은 통로의 개수, $1 \le s, t \le n$은 출발 위치와 목표 위치이다.

다음 줄에는 실수 $n$개 $z_1, z_2, \ldots, z_n$이 주어지고 각 $z_i$는 $-1$ 이상 $1$ 이하이다. $z_i < 0$이면 위치 $i$에 보호력 $-z_i$인 은신 도구가 있다. $z_i > 0$이면 위치 $i$에 탐지 능력 $z_i$인 포식자가 있다. $z_i = 0$이면 위치 $i$에는 포식자도 은신 도구도 없다.

다음 $m$개 줄에는 통로가 하나씩 주어진다. $j$번째 줄의 정수 $p_j$, $q_j$는 $1 \le p_j < q_j \le n$을 만족하고, 문어가 위치 $p_j$에서 $q_j$로, 그리고 $q_j$에서 $p_j$로 바로 이동할 수 있다는 뜻이다. 같은 통로가 두 번 이상 주어질 수 있다. $s$에서 $t$로 가는 방법은 항상 존재한다.

각 데이터 세트마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 데이터 세트의 번호이고 $1$부터 센다. 다음 줄에 문어가 위치 $t$까지 살아서 도달할 확률의 최댓값을 소수점 아래 넷째 자리에서 반올림해 출력한다. 소수점 아래는 정확히 네 자리를 적는다.

데이터 세트를 출력한 뒤에는 빈 줄을 하나 출력한다.