Network Monitoring

Time limit1sMemory limit128 MB

Summary
Given several graphs, decide for each whether a vertex cover of size at most 10 exists.
Level

Medium7 of 10

Topics
Graph, Backtracking, Brute force
Solved
No attempts yet

Problem

An organization wants to monitor every direct communication line in a computer network. Monitoring software can be installed on at most 10 host computers. For the software to work, every direct communication line A-B must have at least one monitored endpoint, either A or B.

For each network, determine whether it is possible to choose at most 10 hosts that cover every communication line.

Input

The input contains several network scenarios. Each scenario has the following format.

  • The first line contains the number of hosts n. (10 <= n <= 2500)
  • Then n lines follow, one for each host. Hosts are named 0, 1, ..., n-1. The first line describes the neighbors of host 0, the second describes the neighbors of host 1, and so on through host n-1.
  • Each of these lines begins with an integer d. (1 <= d < n) This is the number of hosts directly connected to that host. It is followed by d neighbor host numbers, separated by spaces and listed in increasing order. Every neighbor number is valid from 0 to n-1 and is not the host itself.

The final line contains only 0. Do not process that line.

Output

Print one line for each network. Scenario numbers start at 1.

The format is Network n: yes or Network n: no, where n is the scenario number. Print yes if at most 10 hosts can be chosen to monitor every direct communication line; otherwise print no.

Examples1

  1. Example 1

    Input
    11
5 1 3 5 8 10
5 0 2 4 6 9
5 1 3 5 6 10
4 0 2 4 6
4 1 3 5 7
5 0 2 4 6 8
6 1 2 3 5 7 9
4 4 6 8 10
4 0 5 7 9
4 1 6 8 10
4 0 2 7 9
11
10 1 2 3 4 5 6 7 8 9 10
10 0 2 3 4 5 6 7 8 9 10
10 0 1 3 4 5 6 7 8 9 10
10 0 1 2 4 5 6 7 8 9 10
10 0 1 2 3 5 6 7 8 9 10
10 0 1 2 3 4 6 7 8 9 10
10 0 1 2 3 4 5 7 8 9 10
10 0 1 2 3 4 5 6 8 9 10
10 0 1 2 3 4 5 6 7 9 10
10 0 1 2 3 4 5 6 7 8 10
10 0 1 2 3 4 5 6 7 8 9
12
11 1 2 3 4 5 6 7 8 9 10 11
11 0 2 3 4 5 6 7 8 9 10 11
11 0 1 3 4 5 6 7 8 9 10 11
11 0 1 2 4 5 6 7 8 9 10 11
11 0 1 2 3 5 6 7 8 9 10 11
11 0 1 2 3 4 6 7 8 9 10 11
11 0 1 2 3 4 5 7 8 9 10 11
11 0 1 2 3 4 5 6 8 9 10 11
11 0 1 2 3 4 5 6 7 9 10 11
11 0 1 2 3 4 5 6 7 8 10 11
11 0 1 2 3 4 5 6 7 8 9 11
11 0 1 2 3 4 5 6 7 8 9 10
0
    Expected output
    Network 1: yes
Network 2: yes
Network 3: no