관광

다빈치는 식물학을 포함해 여러 분야에 관심이 많았다. 그는 식물 재배와 생태계를 연구하려고 피렌체 주변을 여행할 계획을 세운 적이 있다. 피렌체에는 $n$개의 도시가 있고, 도시 $i$에는 $w_i$종의 식물이 있다. 양방향 도로 $m$개가 각각 두 도시를 잇고 있으며, 이 도로들을 통해 어떤 두 도시든 서로 오갈 수 있다.

다빈치는 도시 $s$에서 출발한다. 그는 한 번에 도로 하나를 타고 인접한 도시 중 한 곳으로 이동할 수 있다. 다만 도로 $u \to v$를 따라 도시 $v$에 도착했다면, 같은 도로를 타고 바로 도시 $u$로 되돌아갈 수는 없다. (같은 도로를 왔다 갔다 하는 여행은 지루하기 때문이다.)

다빈치는 가능한 한 많은 식물 종을 보고 싶어 한다. 즉 $\sum_{\text{방문한 도시 } i} w_i$를 최대화하려고 한다. 같은 도시를 여러 번 방문할 수 있지만, 그 도시의 식물 종은 한 번만 센다. 여행이 어느 도시에서 끝나는지는 상관없다. 이때 여행 중에 볼 수 있는 식물 종의 최대 개수는 얼마인가?

첫 줄에는 데이터 세트의 개수 $K$($1 \le K \le 20$)가 주어지고, 이어서 $K$개의 데이터 세트가 주어진다.

각 데이터 세트의 첫 줄에는 공백으로 구분된 두 정수 $n$, $m$($1 \le n, m \le 1000$)이 주어진다. 둘째 줄에는 $n$개의 정수 $w_i$($0 \le w_i \le 10^6$)가 주어진다. 이어지는 $m$개의 줄에는 $j$번째 도로가 잇는 두 도시 $x_j$, $y_j$($1 \le x_j, y_j \le n$)가 각각 주어진다. 다음 줄에는 다빈치가 출발하는 도시 $s$($1 \le s \le n$)가 하나 주어진다.

어떤 두 도시든 이 도로들을 따라 오갈 수 있다. 같은 도시 쌍을 잇는 도로는 두 개 이상 없으며, 도로가 도시 자기 자신을 잇는 경우도 없다.

각 데이터 세트에 대해 "Data Set x:"라는 행을 출력한다. 여기서 x는 데이터 세트의 번호다. 다음 행에는 다빈치가 볼 수 있는 식물 종의 최대 개수를 출력한다. 각 데이터 세트의 출력 뒤에는 빈 줄을 하나 출력한다.