2146B.md (2918B)
1 Source: https://codeforces.com/problemset/problem/2146/B 2 3 B. Merging the Sets 4 5 time limit per test 6 7 1 second 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 are given $n$ sets $S_1,S_2,\ldots,S_n$, where each element in the sets is an integer between $1$ and $m$. 22 23 You want to choose some of the sets (possibly none or all), such that every integer between $1$ and $m$ is included in at least one of the chosen sets. 24 25 You have to determine whether there exist at least three ways to choose the sets. 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 10^4$). The description of the test cases follows. 30 31 The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 5\cdot 10^4$, $1\le m \leq 10^5$) — the number of sets and the upper bound of the integers in the sets. 32 33 Then $n$ lines follow, the $i$-th line first containing an integer $l_i$ ($1\le l_i\le m$) — the size of set $S_i$. 34 35 Then $l_i$ integers $S_{i,1}, S_{i,2}, \ldots, S_{i, l_i}$ follow in the same line ($1\le S_{i,1} \lt S_{i,2} \lt \cdots \lt S_{i, l_i}\le m$) — the elements of set $S_i$. 36 37 Let $L=\sum\limits_{i=1}^n l_i$. It is guaranteed that: 38 39 * The sum of $n$ over all test cases does not exceed $5\cdot 10^4$; 40 * The sum of $m$ over all test cases does not exceed $10^5$; 41 * The sum of $L$ over all test cases does not exceed $2\cdot 10^5$. 42 43 Output 44 45 For each test case, print "YES" if there exist at least three ways to choose the sets. Otherwise, print "NO". 46 47 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. 48 49 Example 50 51 Input 52 53 ``` 54 6 55 56 3 2 57 58 2 1 2 59 60 1 1 61 62 1 2 63 64 4 10 65 66 3 1 2 3 67 68 2 4 5 69 70 1 6 71 72 4 7 8 9 10 73 74 2 5 75 76 4 1 2 3 4 77 78 4 1 2 3 4 79 80 5 5 81 82 5 1 2 3 4 5 83 84 5 1 2 3 4 5 85 86 5 1 2 3 4 5 87 88 5 1 2 3 4 5 89 90 5 1 2 3 4 5 91 92 5 10 93 94 4 1 2 3 4 95 96 5 1 2 5 6 7 97 98 5 2 6 7 8 9 99 100 4 6 7 8 9 101 102 2 9 10 103 104 5 5 105 106 1 1 107 108 1 2 109 110 1 3 111 112 2 4 5 113 114 1 5 115 ``` 116 117 Output 118 119 ``` 120 YES 121 122 NO 123 124 NO 125 126 YES 127 128 YES 129 130 NO 131 ``` 132 133 Note 134 135 In the first test case, there are $5\ge 3$ possible ways to choose the sets: 136 137 * $S_1$ — both $1$ and $2$ are included in $S_1$; 138 * $S_1$ and $S_2$ — $1$ is included in $S_1$ and $S_2$, and $2$ is included in $S_1$; 139 * $S_1$ and $S_3$ — $1$ is included in $S_1$, and $2$ is included in $S_1$ and $S_3$; 140 * $S_2$ and $S_3$ — $1$ is included in $S_2$, and $2$ is included in $S_3$; 141 * $S_1$, $S_2$, and $S_3$ — $1$ is included in $S_1$ and $S_2$, and $2$ is included in $S_1$ and $S_3$. 142 143 Note that it is invalid to choose $S_2$ only because $2$ is not included in $S_2$. 144 145 In the second test case, the only way is to choose all the sets. 146 147 In the third test case, $5$ does not appear in any of the sets, so there is no way to choose the sets. 148 149 In the fourth test case, choosing any non-empty collection of the sets is valid, so the number of ways is $2^5-1=31\ge3$.