分数: 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