18010번 - Tourism 다국어

Da Vinci has a wide range of interests including botany. He once planned to travel around Florence to study plant domestication and ecosystem. There were n cities in Florence and city i had w_i species of plants, while each of m bidirectional roads connected a pair of cities. It was possible to travel between every pair of cities via these paths.

Da Vinci started from city s and he could travel to one of the adjacent cities through one bidirectional road. However, if he traveled to some city v through road u → v, he would not immediately return to city u using the same road. (It was boring to travel back and forth on the same road!) Da Vinci wanted to see as many species of plants as possible – in other words, he hoped to maximize ∑_{City i is visited} w_i. He could repeatedly visit a city, but the number of species in that city would only count once. What is the maximum number of plant species he could see during the tour, assuming that he did not care about which city to end the trip?

The first line is the number 1 ≤ K ≤ 20 of input data sets, followed by K data sets, each of the following form:

The first line are two integers 1 ≤ n, m ≤ 1000 separated by space. The second line has n integers 0 ≤ w_i ≤ 10⁶. Each of the following m lines contains two integers 1 ≤ x_i, y_i ≤ n, describing the j-th road connecting city x_j and y_j. The next line has a single integer s(1 ≤ s ≤ n) – the city da Vinci started with.

It is possible to travel between any pairs of cities using these roads, no two roads connect the same pair of cities, and no road connects a city to itself.

For each data set, output “Data Set x:” on a line by itself, where x is its number. Then, output the maximum number of plant species da Vinci could see.

Each data set should be followed by a blank line.