B. Erlang

题目描述

小W新学会了一种编程语言Erlang。小W知道Erlang是一个面向并发的程序设计语言，于是就开始拿它写并发的程序了。他写了一个程序，包含一个主进程和 $n$ 个子进程，每个子进程都在不断和主进程通信。按照程序的设定，每次通信都是由子进程给主进程传输一个数。

但是小W的程序现在出现了些偏差，他发现主进程结束不了了。原本的剧本是主进程收到任意一个子进程给它传输一个 $-1$ 就结束，他发现现在变成了主进程收到的所有数里面存在两个数相同，主进程才能结束。

他为了让自己的程序快点结束，他研究了一下那些进程。他发现第 $i$ 个子进程将要给主进程传输 $k_i$ 个数，分别是 $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$。他可以通过操作，控制主进程接受子进程传输的顺序。他每次可以选择一个还没传输完的所有的子进程 $x$，然后让主进程和子进程 $x$ 通信一次，子进程 $x$ 会从它剩下的数中随机选一个传输给主进程。他想要知道在最优策略下，他最坏要通信多少次才能让子进程结束。

一句话题意：现在一共有 $n$ 个可重集 $S_i$，小W每次可以选择一个非空的集合，然后从里面随机抽取一个数，然后把这个数从集合中删掉。当存在两次抽取出来的数相等时结束。小W想要最小化最坏情况下的操作次数。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行第一个整数是 $k_i$，后面跟 $k_i$ 个整数，表示 $a_{i,j}$。

输出格式

输出一行表示最坏情况下的通信次数，若主进程不可能停下来，输出 $-1$。

样例1

input

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

output

2

explanation

先选第一个集合，如果是 $1$ 就选第 $2$ 个集合，如果是 $2$ 就选第 $3$ 个集合，如果是 $3$ 就选第 $4$ 个集合。

限制与约定

Subtask #1 (10 pts)：$n \le 1, \sum k_i \le 10^5$

Subtask #2 (20 pts)：$n \le 5, \sum k_i \le 10$

Subtask #3 (30 pts)：$n, \sum k_i \le 1000$

Subtask #4 (40 pts)：$n, \sum k_i \le 5*10^5$，$1 \le a_{i,j} \le 5*10^5$ 。

时间限制：1s

空间限制：512MB

下载

样例数据下载