← 返回题目列表

Codeforces · 1882/B

B. 集合和联合

中文机器翻译题面 查看原题

您有 $$$n$$$ 组整数 $$$S_{1}、S_{2}、\ldots、S_{n}$$$。如果可以选择集合 $$$S_{1}、S_{2}、\ldots、S_{n}$$$ 中的一些(可能没有),那么我们称集合 $$$S$$$ 是可达到的,使得 $$$S$$$ 等于它们的并集 $$$^{\dagger}$$$。如果您不选择 $$$S_{1}、S_{2}、\ldots、S_{n}$$$ 中的任何一个,则它们的并集是空集。

找出可达到的 $$$S$$$ 中的最大元素数,使得 $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$。

$$$^{\dagger}$$$ 集合 $$$A_1, A_2, \ldots, A_k$$$ 的并集被定义为至少存在于其中一个集合中的元素集合。它由 $$$A_1 \cup A_2 \cup \ldots \cup A_k$$$ 表示。例如,$$$\{2, 4, 6\} \cup \{2, 3\} \cup \{3, 6, 7\} = \{2, 3, 4, 6, 7\}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$)。

下面的 $$$n$$$ 行描述了集合 $$$S_1, S_2, \ldots, S_n$$$。这些行中的第 $$$i$$$ 包含一个整数 $$$k_{i}$$$ ($$$1 \le k_{i} \le 50$$$) — $$$S_{i}$$$ 中的元素数量,后跟 $$$k_{i}$$$ 整数 $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, k_{i}}$$$ ($$$1 \le s_{i, 1} < s_{i, 2} < \ldots < s_{i, k_{i}} \le 50$$$) — $$$S_{i}$$$ 的元素。

输出

对于每个测试用例,打印一个整数 - 可达到的 $$$S$$$ 中的最大元素数量,使得 $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$。

示例

输入 #1

4
3
3 1 2 3
2 4 5
2 3 4
4
4 1 2 3 4
3 2 5 6
3 3 5 6
3 4 5 6
5
1 1
3 3 6 10
1 9
2 1 3
3 5 8 9
1
2 4 28

输出 #1

4
5
6
0

注意

在第一个测试用例中, $$$S = S_{1} \cup S_{3} = \{1, 2, 3, 4\}$$$ 是不等于 $$$S_1 \cup S_2 \cup S_3 = \{1, 2, 3, 4, 5\}$$$ 的最大可达到集合。

在第二个测试用例中,我们可以选择 $$$S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}$$$。

在第三个测试用例中,我们可以选择 $$$S = S_{2} \cup S_{5} = S_{2} \cup S_{3} \cup S_{5} = \{3, 5, 6, 8, 9, 10\}$$$。

在第四个测试用例中,唯一可达到的集合是 $$$S = \varnothing$$$。