Tourism

Da Vinci has a wide range of interests, including botany. He once planned a trip around Florence to study plant domestication and ecosystems. Florence has $n$ cities, and city $i$ has $w_i$ plant species. Each of the $m$ bidirectional roads connects a pair of cities, and it is possible to travel between every pair of cities using these roads.

Da Vinci starts at city $s$. He can move along one road at a time to an adjacent city. However, if he travels to city $v$ via the road $u \to v$, he cannot immediately return to city $u$ on that same road. (Going back and forth on the same road is boring.)

Da Vinci wants to see as many plant species as possible, that is, maximize $\sum_{\text{visited } i} w_i$. He may visit a city more than once, but each city's species are counted only once. He does not care which city the trip ends in. What is the maximum number of plant species he can see during the tour?

The first line contains the number of data sets $K$ ($1 \le K \le 20$), followed by the $K$ data sets.

The first line of each data set contains two integers $n$ and $m$ ($1 \le n, m \le 1000$), separated by a space. The second line contains $n$ integers $w_i$ ($0 \le w_i \le 10^6$). Each of the next $m$ lines contains two integers $x_j$ and $y_j$ ($1 \le x_j, y_j \le n$), describing the $j$-th road that connects cities $x_j$ and $y_j$. The next line contains a single integer $s$ ($1 \le s \le n$), the city where Da Vinci starts.

Any pair of cities can be reached from each other using these roads. No two roads connect the same pair of cities, and no road connects a city to itself.

For each data set, print a line "Data Set x:" where $x$ is the data set number. On the next line, print the maximum number of plant species Da Vinci can see. Print a blank line after each data set.