题目描述

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

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

输入格式

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

$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}$

输出格式

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

题目大意

$n$ 个牌堆，有 $2m$ 张牌，$1\sim m$ 权值的牌各有两张，且同权值的牌不在同一个牌堆中；牌堆顶的牌要求时刻互不相同；现在进行若干次操作，每次选择一个非空牌堆删除牌堆顶，同时要求删除后满足条件，求最多操作多少次。

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

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

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

提示

制約

• $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)$ は互いに相異なる
• 入力される値はすべて整数

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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