G :: Guards

Time Limit: 5 Seconds    Memory Limit: 65536 KB

The royal castles in Molvania follow the design of king Sane, first of his dynasty. He ruled by divide and conquer. Therefore, all castles are built according to a hierarchical pattern based on interconnected buildings. A building consists of halls and corridors that connect halls. Initially, a castle consists of only one building (the main building). When its population grows, the castle is extended as follows: A new peripheral building is constructed, attached to one of the existing buildings. Like any other building, the new building also consists of halls and corridors. An additional corridor is created to connect a hall in the existing building to a hall in the new building. That corridor is the only way to access the new building. The number of halls in a building is at most 10.

 

In times of turmoil, the king monitors all corridors by strategically placing guards in halls. He asks you to determine the least number of guards required to monitor all corridors in the castle (as he wants to keep his personal guard as large as possible). Note that since the last fire, there are no doors in the castle, so we can safely assume that a guard placed in a hall can monitor all connecting corridors.

 

 

Input

The input contains a number of castle descriptions. Within a castle, each hall is identified by a unique number between 1 and 10000. Each castle is recursively defined, starting with a description of the main building:

1. A line containing three integers, representing the number of halls in this building (2 ≤ n ≤ 10), the number of corridors in this building (1 ≤ m ≤ 45), and the number of peripheral buildings that were later attached to this building (0 ≤ w ≤ 10). 

2. For each of the m corridors:

• A line containing two integers (each ≤ 10000), representing the two halls connected by this corridor. Both halls are located inside the current building.

3. For each of the w peripheral buildings:

• A line containing two integers, describing the corridor that leads to this peripheral building. The first integer represents a hall in the current building, while the second integer represents a hall in the peripheral building.

• The structure of the peripheral building and any newer buildings that were later attached to it, described by repeating rules 1 to 3.

The castle is fully connected: any hall is directly or indirectly reachable from any other hall. Corridors with the same start and end hall do not exist, and for every two halls there is at most one corridor between them.

Output

For each castle, print a single line containing a positive integer: the minimum number of guards to place in halls such that all corridors in the castle are monitored.

 

Sample Input

5 8 2 
1 2 
2 4 
3 4 
1 3 
1 5 
2 5 
3 5 
4 5 
1 6 
3 3 0 
6 7 
7 8 
8 6 
5 10 
3 2 2 
10 11 
10 12 
11 13 
2 1 0 
13 9 
11 14 
3 2 0 
14 15 
14 16

Sample Output

8
Submit

Source: NWERC 2012