시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 2 2 40.000%

문제

A spy agency wants to monitor all communications in a computer network. They have a budget for at most 10 installations of spying software on 10 of the host computers on the network. For the software to work properly each communication line A–B must have at least one host A or B being monitored.

입력

Input will consist of a number of network scenarios. Each scenario will contain:

  • An integer n (10 ≤ n ≤ 2500) on a line on its own, giving the number of hosts in the network.
  • A line of data for each host (thus n lines in total) giving the list of other hosts to which the host has a direct communication line. The hosts are named 0, 1, . . . , n−1; the first line of data gives the neighbours of host 0, the second those of host 1, and so on up to host n − 1.
    Each of these lines consists of an integer d (1 ≤ d < n) which is the number of neighbours host k has, followed by d integers which are the neighbouring hosts’ names, separated by spaces. The neighbours will be given in numerical order, and will each be valid host names in 0, 1, . . . n − 1 other than k.
    (Note that each of these input lines may thus be up to 2500×5 characters in length.)

The last line of input will be a ‘0’ on a line by itself. This line should not be processed.

출력

Output will consist of one line for each input network, indicating whether the network can be successfully spied upon by infecting 10 nodes. Each line of the output will consist of ‘Network n: ’, where n is the scenario number, starting at 1, followed by ‘yes’ or ‘no’.

예제 입력

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

예제 출력

Network 1: yes
Network 2: yes
Network 3: no

힌트