SP25476 TAP2015F - Induced favoritism

**\[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at** **** **\]** In a kingdom far, far away there are N cities numbered 1 through N, some pairs of cities being connected by roads. When two cities are directly connected by a road, we will say these cities are neighbors. As a result of the careful planning of its monarchs, the kingdom's road system has very special characteristics. We know there are no two cities connected by more than one road, and that all roads connect different cities. Another very peculiar property of the roads is that there is exactly one path between any two cities, consisting of a sequence of roads connecting neighboring cities from the initial to the final one.

There are multiple test cases in the input file. For each test case, the first line contains two integers **N** and **E**, representing respectively the number of cities and the number of curling teams in the kingdom (**2 and **1 ). The following **E** lines describe the riot indices between the curling teams. Each of these lines contains **E** integers, the **j**-th integer of the **i**-th of these lines being **D $ _{ij} $** , the riot index between teams **i** and **j** (**0 with **D $ _{ij} $ = D $ _{ji} $** for **i, j = 1, 2, ..., E**).****** The following **E** lines describe the favorite teams of the cities which have already chosen one. The **i**-th of these lines starts with a non-negative integer **K $ _{i} $** followed by a list of **K $ _{i} $** cities whose favorite team is number **i** (**0 for **i = 1, 2, ..., E**). No city has more than one favorite team, and there are no repeated cities in the lists.** The last **N-1** lines describe the roads between the kingdom's cities. Each of them contains two integers **A** and **B**, indicating that there is a road between city **A** and city **B** (**1 with **A ≠ B**). The roads are bidirectional and there are no repeated roads in the input. It is guaranteed that there is a unique path between every pair of cities, possibly going through other intermediate cities.**

For each test case, print one line containing an integer representing the minimum value of the national riot index that can be achieved by optimally assigning the favorite teams.