分数: 2000 点
问题陈述
有 N 一副纸牌,每张纸牌之间都有一个整数 1 和 M,包含在内,写在上面。的 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 \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),恰好有两对 (i,j) 这样 x=A_{i,j},以及两个值 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
如果你最初在第一副牌上执行操作,则该副牌上的卡牌上的数字变为 2, 3, 4 按从上到下的顺序。此后,您将无法在第一层甲板上再次执行该操作,因为第一层甲板和第二层甲板都会有 3 在他们的顶牌上。同样,您也无法在第二层进行操作。因此,如果您从第一副牌开始执行操作,则只能执行一次。
即使您从第二副牌上执行操作开始,也只能执行一次。因此,答案是 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
有时无法执行任何操作。
示例输入 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