题目描述

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$.

4 2
1 2
3 4

1 2
2 1 2
2 3 1

提示

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