AT_agc062_f [AGC062F] Preserve Distinct

[problemUrl]: https://atcoder.jp/contests/agc062/tasks/agc062_f $ 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} $

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

### 制約 - $ 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 $ 回も操作できないこともあります。