Water Contamination

While the rain, mud, and their immediate effects (in particular, drownings) often cause the most initial damage, some of the long-term danger of hurricanes results from water contamination and diseases. High water levels can transport dangerous sewage or other contaminated substances from where they are normally kept to places where people are. Drinking contaminated water is dangerous, of course. So it is important to keep contaminants contained, even when the water levels rise.

We model this problem as follows. You are given a list of places with contamination (such as sewage plants, garbage deposits, biohazard labs) and a list of places that must be protected (hospitals, city water processing plants), as well as connections between places. These connections are the ones that would be flooded and thus transport contaminants during or after the hurricane. Your goal is to find the smallest number of connections that must be blocked (for example, with large piles of sandbags) to protect all important places from all contaminants.

The first line contains a number 1 ≤ K ≤ 100, the number of data sets in the input file. K data sets follow, each in the form below.

The first line of a data set contains two integers n and c, where 1 ≤ n ≤ 500 is the number of locations and 0 ≤ c ≤ 5000 is the number of connections.

The next line contains n integers 0 ≤ t_i ≤ 2, giving the type of location i. 0 means the location is neither contaminated nor important, 1 means it is contaminated (but not important), and 2 means it is important, that is, it must be protected (and is not contaminated).

Next come c lines, each with two integers 1 ≤ s_j, t_j ≤ n. This means there is a connection between s_j and t_j along which contaminants could spread, in either direction.

For each data set, output "Data Set x:" on a line by itself, where x is the data set number. Then output the number of connections that must be blocked so that no important location becomes contaminated.

Each data set is followed by a blank line.