← 返回题目列表

AtCoder · awc0013_e

E. 兼职工作轮班分配

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥兼职店长,负责轮班管理。下周有 N 他想要为其分配工作人员的时间段。

有 M 兼职人员候选人,编号自 1 to M。对于每个时段 i (1 \leq i \leq N), K_i 给出了在该时间段内可以工作的候选人编号。具体来说,候选人可以参加的时间段 i 已编号 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i}.

对于每个时间段,Takahashi 选择要么只分配一名可用于该时间段的候选人,要么不分配任何人。然而,同一候选者不能被分配到多个时隙。也就是说,每个候选者最多可以被分配到一个时隙。

查找可以为候选分配的最大时隙数。

约束

  • 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}
  • 第一行包含时隙数 N 及考生人数 M,用空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每个时隙可用的候选者的信息。
  • 的 树的 (1 + i)第行 (1 \leq i \leq N) 包含候选人数量 K_i 可用于时段 i,后跟其候选编号 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i},用空格分隔。如果 K_i = 0,仅值 该行给出了 0 为 K_i 。

输出

在一行上打印可以为候选者分配的最大时隙数。


示例输入 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