Codeforces Round 899 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

brute force

constructive algorithms

greedy

*1300

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Sets and Union

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have $$$n$$$ sets of integers $$$S_{1}, S_{2}, \ldots, S_{n}$$$. We call a set $$$S$$$ attainable, if it is possible to choose some (possibly, none) of the sets $$$S_{1}, S_{2}, \ldots, S_{n}$$$ so that $$$S$$$ is equal to their union$$$^{\dagger}$$$. If you choose none of $$$S_{1}, S_{2}, \ldots, S_{n}$$$, their union is an empty set.

Find the maximum number of elements in an attainable $$$S$$$ such that $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$.

$$$^{\dagger}$$$ The union of sets $$$A_1, A_2, \ldots, A_k$$$ is defined as the set of elements present in at least one of these sets. It is denoted by $$$A_1 \cup A_2 \cup \ldots \cup A_k$$$. For example, $$$\{2, 4, 6\} \cup \{2, 3\} \cup \{3, 6, 7\} = \{2, 3, 4, 6, 7\}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$).

The following $$$n$$$ lines describe the sets $$$S_1, S_2, \ldots, S_n$$$. The $$$i$$$-th of these lines contains an integer $$$k_{i}$$$ ($$$1 \le k_{i} \le 50$$$) — the number of elements in $$$S_{i}$$$, followed by $$$k_{i}$$$ integers $$$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$$$) — the elements of $$$S_{i}$$$.

Output

For each test case, print a single integer — the maximum number of elements in an attainable $$$S$$$ such that $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$.

Example

Input

433 1 2 32 4 52 3 444 1 2 3 43 2 5 63 3 5 63 4 5 651 13 3 6 101 92 1 33 5 8 912 4 28

Output

4 5 6 0

Note

In the first test case, $$$S = S_{1} \cup S_{3} = \{1, 2, 3, 4\}$$$ is the largest attainable set not equal to $$$S_1 \cup S_2 \cup S_3 = \{1, 2, 3, 4, 5\}$$$.

In the second test case, we can pick $$$S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}$$$.

In the third test case, we can pick $$$S = S_{2} \cup S_{5} = S_{2} \cup S_{3} \cup S_{5} = \{3, 5, 6, 8, 9, 10\}$$$.

In the fourth test case, the only attainable set is $$$S = \varnothing$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 09:46:09 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|