We claim that a graph is good if and only if its complement is bipartite.

Taking complement, the condition is equivalent with each subset contains an independent set of size at least half.

If there is an odd cycle, the maximal independent set is smaller than half if we only consider the vertices in this cycle.

On the other hand, if the complement is bipartite, for each subset, the bigger part is an independent set of size at least half.

To implement this, directly output No if \(m < \binom n2 -\lfloor\frac{n^2}4\rfloor\), and check by brute force otherwise. This works in \(O(m)\) time. Or we can just output No if \(n \ge 2002\), which also passes in given time.