P15660 [ICPC 2025 Jakarta R] Two Sets

You are given an undirected graph with $N$ vertices and $M$ edges, with vertices numbered from $1$ to $N$. You have to select two integers $p$ and $q$ such that: - $N < (p + 1)(q + 1)$ - There exists a non-empty set of vertices $S_1$ such that for every vertex $u \in S_1$, there are $\textbf{at least}$ $p$ other vertices in $S_1$ that share an edge with $u$. - There exists a set of vertices $S_2$ of size $\textbf{at least}$ $q$ such that for every vertex $u \in S_2$, there are no vertices in $S_2$ that share an edge with $u$. You have to find $p$, $q$, along with any $S_1$ and $S_2$ that satisfy the requirements above. It can be proven that such $p$ and $q$ always exist.

The first line contains two integers $N$ and $M$ ($1 \leq N \leq 2000$; $0 \leq M \leq \min(\frac{N(N-1)}{2}, 200\;000$)). Each of the next $M$ lines contains two integers $u$ and $v$ ($1 \leq u < v \leq N$) representing the two vertex numbers that are connected by an edge. All the given edges are different.

The first line contains two integers $p$ and $q$. The second line contains an integer $|S_1|$ followed by $|S_1|$ integers representing the vertex numbers in $S_1$. The third line contains an integer $|S_2|$ followed by $|S_2|$ integers representing the vertex numbers in $S_2$.

$\textit{Explanation of Sample 1:}$ You selected $p = 1$, $q = 2$, $S_1 = \{1, 2\}$, and $S_2 = \{1, 3\}$.