1882B.md (2269B)
1 Source: https://codeforces.com/problemset/problem/1882/B 2 3 B. Sets and Union 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You 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. 22 23 Find the maximum number of elements in an attainable $S$ such that $S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$. 24 25 $^{\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\}$. 26 27 Input 28 29 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. 30 31 The first line of each test case contains a single integer $n$ ($1 \le n \le 50$). 32 33 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} \lt s_{i, 2} \lt \ldots \lt s_{i, k_{i}} \le 50$) — the elements of $S_{i}$. 34 35 Output 36 37 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}$. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 46 3 47 48 3 1 2 3 49 50 2 4 5 51 52 2 3 4 53 54 4 55 56 4 1 2 3 4 57 58 3 2 5 6 59 60 3 3 5 6 61 62 3 4 5 6 63 64 5 65 66 1 1 67 68 3 3 6 10 69 70 1 9 71 72 2 1 3 73 74 3 5 8 9 75 76 1 77 78 2 4 28 79 ``` 80 81 Output 82 83 ``` 84 4 85 5 86 6 87 0 88 ``` 89 90 Note 91 92 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\}$. 93 94 In the second test case, we can pick $S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}$. 95 96 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\}$. 97 98 In the fourth test case, the only attainable set is $S = \varnothing$.