35171번 - 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 at least $p$ other vertices in $S_1$ that share an edge with $u$.
• There exists a set of vertices $S_2$ of size 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}, 200000$)). 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$.