E - Group Division and Virus Infection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は N 台のコンピュータからなる社内ネットワークの管理者です。各コンピュータには 1 から N までの番号が付いています。

このネットワークには M 種類のコンピュータウイルスが存在することが判明しました。各ウイルスには 1 から M までの番号が付いています。

ウイルス j（1 \leq j \leq M）は、特定のコンピュータの集合 S_j に感染する能力を持っています。S_j は空であることもあります。

高橋君は、N 台のコンピュータをいくつかのサブネットワーク（グループ）に分割し、グループ間の通信を遮断するファイアウォールを設置することで被害を抑えようとしています。ここでグループ分けとは、N 台のコンピュータの集合を 1 つ以上の空でないグループに分けることであり、すべてのコンピュータがちょうど 1 つのグループに属するものとします。グループの数は 1 以上 N 以下の任意の数を選べます。

各ウイルスの被害は、以下のルールにより互いに独立に判定されます。

  • ウイルス j の感染対象 S_j に含まれるコンピュータがすべて同一のグループに属している場合、ウイルス j はファイアウォールに阻まれることなくグループ内で拡散し、S_j に含まれるすべてのコンピュータが被害を受けます。
  • ウイルス j の感染対象 S_j に含まれるコンピュータが 2 つ以上の異なるグループにまたがっている場合、ウイルス j はファイアウォールによって拡散が阻止され、S_j のどのコンピュータにも被害を与えません。

ここで、S_j が空の場合や S_j に含まれるコンピュータが 1 台のみの場合は、S_j のコンピュータはすべて同一のグループに属しているとみなします。（S_j が空の場合、被害を受けるコンピュータはありません。S_j に 1 台のみ含まれる場合、そのコンピュータはどのグループ分けでも必ず被害を受けます。）

すべての M 種類のウイルスによる被害を考えたとき、1 種類以上のウイルスから被害を受けるコンピュータの台数（同じコンピュータが複数のウイルスから被害を受けても 1 台と数えます）を最小化したいです。

最適なグループ分けを行ったときの、被害を受けるコンピュータの台数の最小値を求めてください。

制約

  • 1 \leq N \leq 15
  • 1 \leq M \leq 500
  • 0 \leq k_j \leq N（1 \leq j \leq M）
  • 1 \leq s_{j,i} \leq N（1 \leq j \leq M, 1 \leq i \leq k_j）
  • ウイルス j の感染対象のコンピュータ番号 s_{j,1}, s_{j,2}, \ldots, s_{j,k_j} はすべて異なる
  • 入力はすべて整数である

入力

N M
k_1 s_{1,1} s_{1,2} \ldots s_{1,k_1}
k_2 s_{2,1} s_{2,2} \ldots s_{2,k_2}
\vdots
k_M s_{M,1} s_{M,2} \ldots s_{M,k_M}
  • 1 行目には、コンピュータの台数を表す N と、ウイルスの種類数を表す M が、スペース区切りで与えられる。
  • 2 行目から M 行にわたって、各ウイルスの情報が与えられる。
  • 1 + j 行目では、ウイルス j の感染対象のコンピュータの台数 k_j と、それらのコンピュータの番号 s_{j,1}, s_{j,2}, \ldots, s_{j,k_j} がスペース区切りで与えられる。k_j = 0 の場合、その行には k_j のみが与えられる。

出力

最適なグループ分けを行ったときの、被害を受けるコンピュータの台数の最小値を 1 行で出力せよ。

入力例 1

3 3
2 1 2
2 2 3
1 1

出力例 1

1

入力例 2

4 4
0
2 1 2
2 3 4
4 1 2 3 4

出力例 2

0

入力例 3

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

出力例 3

1

入力例 4

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

出力例 4

2

入力例 5

1 1
0

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is the administrator of a corporate network consisting of N computers. Each computer is numbered from 1 to N.

It has been discovered that M types of computer viruses exist in this network. Each virus is numbered from 1 to M.

Virus j (1 \leq j \leq M) has the ability to infect a specific set of computers S_j. S_j may be empty.

Takahashi wants to mitigate the damage by dividing the N computers into several subnetworks (groups) and installing firewalls to block communication between groups. Here, a grouping means partitioning the set of N computers into one or more non-empty groups, where every computer belongs to exactly one group. The number of groups can be any number from 1 to N.

The damage from each virus is determined independently according to the following rules:

  • If all computers in virus j's infection target S_j belong to the same group, virus j spreads within the group without being blocked by any firewall, and all computers in S_j are damaged.
  • If the computers in virus j's infection target S_j are spread across two or more different groups, virus j's spread is blocked by the firewall, and no computer in S_j is damaged.

Here, if S_j is empty or contains only one computer, all computers in S_j are considered to belong to the same group. (If S_j is empty, no computer is damaged. If S_j contains only one computer, that computer is always damaged regardless of the grouping.)

Considering the damage from all M types of viruses, we want to minimize the number of computers that are damaged by one or more viruses (even if the same computer is damaged by multiple viruses, it is counted as one).

Find the minimum number of damaged computers when the optimal grouping is chosen.

Constraints

  • 1 \leq N \leq 15
  • 1 \leq M \leq 500
  • 0 \leq k_j \leq N (1 \leq j \leq M)
  • 1 \leq s_{j,i} \leq N (1 \leq j \leq M, 1 \leq i \leq k_j)
  • The computer numbers s_{j,1}, s_{j,2}, \ldots, s_{j,k_j} in the infection target of virus j are all distinct
  • All input values are integers

Input

N M
k_1 s_{1,1} s_{1,2} \ldots s_{1,k_1}
k_2 s_{2,1} s_{2,2} \ldots s_{2,k_2}
\vdots
k_M s_{M,1} s_{M,2} \ldots s_{M,k_M}
  • The first line contains N, the number of computers, and M, the number of virus types, separated by a space.
  • The following M lines provide information about each virus.
  • The (1 + j)-th line contains k_j, the number of computers in the infection target of virus j, followed by the computer numbers s_{j,1}, s_{j,2}, \ldots, s_{j,k_j}, separated by spaces. If k_j = 0, only k_j is given on that line.

Output

Print in one line the minimum number of damaged computers when the optimal grouping is chosen.

Sample Input 1

3 3
2 1 2
2 2 3
1 1

Sample Output 1

1

Sample Input 2

4 4
0
2 1 2
2 3 4
4 1 2 3 4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

1

Sample Input 4

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

Sample Output 4

2

Sample Input 5

1 1
0

Sample Output 5

0