配点 : $2000$ 点

問題文

$1$ 以上 $M$ 以下の整数が書かれているカードからなる山札が $N$ 個あります。 $i\ (1\leq i \leq N)$ 番目の山札は $K_i$ 枚のカードからなり、上から $j$ 枚目のカードに書かれている整数は $A_{i,j}\ (1\leq j \leq K_i)$ です。

カードに書かれている整数ははじめ、以下の制約を満たします。

• 各整数 $x\ (1\leq x \leq M)$ について、$x$ が書かれているカードは $N$ 個の山札のうちちょうど $2$ つの山札に $1$ 枚ずつ存在する
• 各山札の一番上のカードに書かれている整数は互いに相異なる

$N$ 個の山札に対し以下のような操作を考えます。

• カードが残っている山札を $1$ つ選び、一番上のカードを捨てる。ただし、カードを捨てた後、カードが残っている各山札の一番上のカードに書かれている整数は互いに相異なっていなければならない

最大で何回操作を行えるか求めてください。

制約

• $2 \leq N \leq M$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq K_i \leq M$
• $1 \leq A_{i,j} \leq M$
• 各整数 $x\ (1\leq x \leq M)$ に対し、$x=A_{i,j}$ が成り立つ $i,j$ の組はちょうど $2$ つ存在し、$2$ つの $i$ は互いに相異なる
• $A_{i,1}\ (1\leq i \leq N)$ は互いに相異なる
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$

$K_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,K_1}$

$K_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,K_2}$

$\vdots$

$K_N$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,K_N}$

出力

答えを出力してください。

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

1

はじめに $1$ 番目の山札に対して操作すると、山札のカードに書かれている整数は上から順に $2,3,4$ となります。この状態から $1$ 番目の山札に対して操作すると、$1$ 番目の山札も $2$ 番目の山札も一番上のカードに書かれている整数が $3$ になってしまうため、$1$ 番目の山札に操作できません。同様に $2$ 番目の山札に対しても操作できません。よってはじめに $1$ 番目の山札に対して操作した場合、操作できるのは $1$ 回だけです。

はじめに $2$ 番目の山札に対して操作した場合も操作できるのは $1$ 回だけなので、答えは $1$ です。

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

12

適切に操作をすることで全てのカードを捨てることができます。

3 3
2 1 2
2 2 3
2 3 1

0

$1$ 回も操作できないこともあります。

12 40
4 35 39 11 21
7 31 29 16 15 30 32 34
4 21 27 38 40
11 17 28 26 23 33 22 3 36 8 1 20
1 30
4 40 38 24 6
8 8 36 9 10 5 7 20 4
10 5 10 9 3 22 33 23 26 28 17
4 15 16 29 31
11 19 13 12 18 25 2 39 35 7 14 37
3 4 1 14
13 24 27 11 2 25 18 12 13 19 32 37 6 34

53