Merging the Sets

We need decide whether there are at least three subsets of the given sets whose union covers every number from $1$ to $m$.

Counting set covers in general is ugly. Luckily, the target is tiny: just distinguish $0,1,2$ from $\ge 3$. So we should not count covers like a maniac. We only need a structural reason that gives us three valid choices.

Forced sets

For each number $x$, let $cnt[x]$ be the number of given sets containing $x$.

If $cnt[x]=0$, then $x$ is impossible to cover. Answer is immediately NO.

If $cnt[x]=1$, then the single set containing $x$ is mandatory. Any valid selection must include it, because otherwise $x$ disappears. So every set that contains at least one uniquely appearing element is forced.

Example: if $7$ appears only in $S_4$, then $S_4$ must be chosen. Doesn’t matter what else is happening. $S_4$ is not optional.

Now consider a set that contains no uniquely appearing element. Every element inside it appears somewhere else too. That means if we choose all sets and then remove this set, the union still covers everything. Every element it contributed is still covered by another set.

Call such a set optional-removable.

Why two optional-removable sets are enough

Suppose every number appears at least once, and there are two optional-removable sets, say $A$ and $B$.

Then these three choices are all valid:

• choose all sets;
• choose all sets except $A$;
• choose all sets except $B$.

Those are three distinct valid ways. So the answer is YES.

Notice we are not even trying to be fancy and remove both. We only need three ways, and boom, done.

Why fewer than two is not enough

All forced sets must appear in every valid selection.

Only optional-removable sets can possibly vary freely. If there are:

• $0$ such sets, then every set is forced, so there is only one possible valid selection: all sets.
• $1$ such set, then the forced sets are always chosen, and this one set may be included or excluded. That gives at most two valid selections.

So with fewer than two optional-removable sets, reaching three ways is impossible.

Therefore the whole problem collapses to:

1. Count occurrences of each number.
2. If any number has occurrence $0$, answer NO.
3. Count how many sets contain no number with occurrence $1$.
4. Answer YES iff that count is at least $2$.

Complexity

We read and inspect every listed element a constant number of times.

The complexity is $O(n+m+L)$ per test case, where $L=\sum l_i$. This fits easily inside the limits.