VU algoritmavimo seminaras (2005 ruduo)

We have a remote village with n ≤ 20 houses (h₀, h₁, h₂, ..., h_n-1) and several secure telephone lines linking neighbouring houses (there is exactly one line between each pair of neighbouring houses). For any pair of houses h_i and h_j there is at least one path of telephone lines connecting them (this can be viewed as an undirected connected graph with houses as vertices and lines as edges).

Gossip can travel over telephone lines. Each house can call at most one neighbour house at a time. Calls may begin at the beginning of each hour (e.g., 9 am, 1 pm, 6 pm, etc), and last for exactly one hour. The local telephone company charges a fortune for each call, but has a quirk that any number of calls can be made in parallel at the same price as any single call.

Given this scenario, we want to find the minimum total price (minimum number of used hours) to disseminate some gossip from house h₀ to all other houses.

Input Format

The input involves a series of scenarios. Within each scenario the first line has an integer number n, the number of houses. This first line is followed by n other lines, one for each house, in the order h₀, h₁, h₂, ..., h_n-1. Each house line contains a list of indices of its neighbouring houses (in no particular order), separated by single spaces.

The series is terminated by a scenario with n=0, which isn't processed.

Sample Input

4
1 2
0 3
3 0
1 2
7
1 2 3
0 2
0 1 3 4
0 2
6 2 5
4 6
4 5
0

Output Format

The output must be "Village s: p", where s is the scenario sequence number starting at 1 and p is the answer for each input village (use single spaces as separators, i.e., one space after the word "Village" and another space after the colon ":").

Sample Output

Village 1: 2
Village 2: 4