F - Preserve Distinct Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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}

出力

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

入力例 1

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

出力例 1

1

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

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

入力例 2

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

出力例 2

12

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

入力例 3

3 3
2 1 2
2 2 3
2 3 1

出力例 3

0

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

入力例 4

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

出力例 4

53

Score : 2000 points

Problem Statement

There are N decks of cards, each card in which has an integer between 1 and M, inclusive, written on it. The i-th deck (1\leq i \leq N) contains K_i cards, and the number written on the j-th card from the top is A_{i,j}\ (1\leq j \leq K_i).

Initially, the integers written on the cards satisfy the following conditions:

  • For each integer x\ (1\leq x \leq M), there are exactly two cards with x written on them, each in a different deck.
  • The integers written on the top cards of all the decks are pairwise different.

We can perform the following operation on the N decks:

  • Choose a deck that still has cards and discard the top card. After discarding, the integers written on the top cards of the decks that still have cards must remain pairwise different.

Determine the maximum number of times this operation can be performed.

Constraints

  • 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
  • For each integer x\ (1\leq x \leq M), there are exactly two pairs (i,j) such that x=A_{i,j}, and the two values of i are different.
  • A_{i,1}\ (1\leq i \leq N) are pairwise different.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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}

Output

Print the answer.

Sample Input 1

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

Sample Output 1

1

If you initially perform the operation on the first deck, the numbers on the cards of this deck become 2, 3, 4 in order from the top. After this, you may not perform the operation again on the first deck because both the first and second decks would have 3 on their top cards. Similarly, you cannot perform the operation on the second deck either. Therefore, if you start by performing the operation on the first deck, you can only do it once.

Even if you start by performing the operation on the second deck, you can only do it once. Therefore, the answer is 1.

Sample Input 2

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

Sample Output 2

12

By operating properly, it is possible to discard all the cards.

Sample Input 3

3 3
2 1 2
2 2 3
2 3 1

Sample Output 3

0

There are cases when no operation can be performed.

Sample Input 4

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

Sample Output 4

53