Castle Guards

A king wants to build a huge castle to proclaim the greatness of his kingdom. The castle is a collection of interconnected buildings, and each building consists of several halls and the corridors that connect those halls.

At first the castle consists of a single building, called the main building. Whenever the kingdom's population grows, the castle expands as follows. A new annex building is constructed and connected to one already existing building. Like every other building, the new building is made of halls and corridors. In addition, one new corridor is built joining some hall of the existing building to some hall of the new building; this corridor is the only passage into the new building.

A building can contain at most $10$ halls. Consequently the buildings are connected in the shape of a tree.

The king wants to place guards on halls, strategically, so that every corridor of the castle is watched. A guard watches every corridor connected to the hall on which the guard stands, so a corridor is watched whenever at least one of the two halls it joins holds a guard. Because the king wants to keep as many people as possible for his personal protection, he wants to minimize the number of guards needed to watch every corridor of the castle - both the corridors inside buildings and the corridors that bridge one building to another.

The input consists of several test cases. Each castle is defined recursively and is given starting from its main building. Every hall is identified by an integer between $1$ and $10000$, and within one castle the hall numbers are distinct.

A single building is described as follows. The first line contains the number of halls $n$ ($2 \le n \le 10$) that make up the building, the number of internal corridors $m$ ($1 \le m \le 45$), and the number of annex buildings $w$ ($0 \le w \le 10$) directly attached to it.

The next $m$ lines describe the building's internal corridors. Each line gives the numbers of the two halls joined by a corridor; the two halls are always in the same building.

After that, the $w$ annex buildings are given one after another. For each annex building, one line first gives two integers - a hall number of the current building and a hall number of the annex building - describing the corridor that joins the two buildings. That line is immediately followed by the description of the annex building, in the same recursive format as the main building.

The castle is always fully connected: any two halls are connected directly or through other halls. There is at most one corridor between any two halls. The input continues until end of file, and each test case represents one complete castle.

For each test case, print on its own line the minimum number of guards needed to watch every corridor of the castle.