E - アルバイトのシフト割り当て 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、アルバイト先の店長としてシフト管理を任されています。来週、スタッフを配置したい時間帯が N 個あります。

アルバイトスタッフの候補者は M 人おり、1 から M までの番号が付いています。各時間帯 i (1 \leq i \leq N) に対して、その時間帯に勤務可能な候補者の番号が K_i 個与えられます。具体的には、時間帯 i に勤務可能な候補者の番号は C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} です。

高橋君は、各時間帯に対して、その時間帯に勤務可能な候補者の中から 1 人を割り当てるか、誰も割り当てないかのいずれかを選びます。ただし、同じ候補者を複数の時間帯に割り当てることはできません。すなわち、各候補者は高々 1 つの時間帯にのみ割り当てることができます。

候補者を割り当てた時間帯の数の最大値を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq M \leq 100
  • 0 \leq K_i \leq M (1 \leq i \leq N)
  • 1 \leq C_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq K_i)
  • 各 i について、C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} はすべて異なる
  • 入力はすべて整数

入力

N M
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_N C_{N,1} C_{N,2} \ldots C_{N,K_N}
  • 1 行目には、時間帯の数 N と候補者の数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目には、各時間帯に勤務可能な候補者の情報が与えられる。
  • 1 + i 行目 (1 \leq i \leq N) には、時間帯 i に勤務可能な候補者の人数 K_i と、その候補者の番号 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} がスペース区切りで与えられる。K_i = 0 の場合、その行には K_i の値 0 のみが与えられる。

出力

候補者を割り当てた時間帯の数の最大値を 1 行で出力してください。

入力例 1

3 3
2 1 2
2 2 3
2 1 3

出力例 1

3

入力例 2

4 5
3 1 2 3
2 2 4
1 5
2 3 4

出力例 2

4

入力例 3

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

出力例 3

5

Score : 466 pts

Problem Statement

Takahashi has been put in charge of shift management as the store manager at his part-time job. Next week, there are N time slots for which he wants to assign staff.

There are M part-time staff candidates, numbered from 1 to M. For each time slot i (1 \leq i \leq N), K_i candidate numbers who are available to work during that time slot are given. Specifically, the candidates available for time slot i are numbered C_{i,1}, C_{i,2}, \ldots, C_{i,K_i}.

For each time slot, Takahashi chooses either to assign exactly one candidate who is available for that time slot, or to assign no one. However, the same candidate cannot be assigned to multiple time slots. That is, each candidate can be assigned to at most one time slot.

Find the maximum number of time slots to which a candidate can be assigned.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq M \leq 100
  • 0 \leq K_i \leq M (1 \leq i \leq N)
  • 1 \leq C_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq K_i)
  • For each i, C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} are all distinct
  • All input values are integers

Input

N M
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_N C_{N,1} C_{N,2} \ldots C_{N,K_N}
  • The first line contains the number of time slots N and the number of candidates M, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about the candidates available for each time slot is given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the number of candidates K_i available for time slot i, followed by their candidate numbers C_{i,1}, C_{i,2}, \ldots, C_{i,K_i}, separated by spaces. If K_i = 0, only the value 0 for K_i is given on that line.

Output

Print the maximum number of time slots to which a candidate can be assigned, on a single line.

Sample Input 1

3 3
2 1 2
2 2 3
2 1 3

Sample Output 1

3

Sample Input 2

4 5
3 1 2 3
2 2 4
1 5
2 3 4

Sample Output 2

4

Sample Input 3

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

Sample Output 3

5