問題
あるアルバイト先では、$N$人の学生と$M$種類のシフトがあります。 各学生は、自分が希望するシフトをいくつか挙げています。 ただし、各学生は最大で1つのシフトにしか入れず、各シフトには1人までしか割り当てられません。 そこで、できるだけ多くの学生を、自分の希望するシフトに1つだけ割り当てたいと考えています。 あなたの仕事は、与えられた希望に基づいて、希望が叶う学生の最大人数を求めることです。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$
$k_1$ $S_{1,1}$ $S_{1,2}$ ... $S_{1,k_1}$
$k_2$ $S_{2,1}$ $S_{2,2}$ ... $S_{2,k_2}$
:
$k_N$ $S_{N,1}$ $S_{N,2}$ ... $S_{N,k_N}$
1行目に学生の人数$N$、シフトの数$M$
2行目以降に各学生の希望するシフト数$k_i$と希望するシフト番号$S_{i,j}$
出力
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N, M \leq 10^5$
- $1 \leq k_i \leq 50$ $(1 \leq i \leq N)$
- $1 \leq S_{i,j} \leq M$ $(1 \leq i \leq N)(1 \leq j \leq k_i)$ 入力はすべて整数
入出力例
入力例1
4 4 2 1 2 2 2 3 1 3 1 4
出力例1
4
入力例2
3 3 1 2 1 2 1 2
出力例2
1
入力例3
5 3 1 1 1 2 1 3 1 2 1 3
出力例3
3