A. NP-难问题
每个测试的时间限制：$2$ 秒
内存限制：$256$ 兆字节

最近，Pari 和 Arya 做了一些关于 NP-难问题的研究，并发现最小顶点覆盖问题非常有趣。

假设给定图 $G$。其顶点的子集 $A$ 被称为该图的顶点覆盖，如果对于每条边 $uv$，它的至少一个端点属于该集合，即 $u \in A$ 或 $v \in A$（或两者同时成立）。

Pari 和 Arya 在一场团队竞赛中获得了一幅漂亮的无向图作为奖励。现在，他们需要把这幅图分成两部分，并且两人的图部分都要是一个顶点覆盖。

他们已经同意交给你他们的图，而你需要找到两个不相交的顶点子集 $A$ 和 $B$，使得 $A$ 和 $B$ 都是顶点覆盖，否则说明不可能。每个顶点最多可以交给其中一人（你也可以自己留下）。

输入
第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 100\,000$，$1 \le m \le 100\,000$）—— 分别表示获奖图的顶点数和边数。

接下来 $m$ 行，每行包含一对整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示 $u_i$ 与 $v_i$ 之间的一条无向边。
保证图中没有自环和重边。

输出
如果无法按 Pari 和 Arya 的要求拆分图，输出 -1（不带引号）。

如果存在两个不相交的顶点子集，且它们都是顶点覆盖，则输出它们的描述。
每个描述包含两行：

• 第一行是一个整数 $k$，表示该顶点覆盖中的顶点数；
• 第二行是 $k$ 个整数，表示这些顶点的编号。

注意由于 $m \ge 1$，顶点覆盖不能为空。

示例

输入

4 2
1 2
2 3

输出

1
2 
2
1 3 

输入

3 3
1 2
2 3
1 3

输出

-1

说明
在第一个样例中，你可以把顶点 $2$ 交给 Arya，把顶点 $1$ 和 $3$ 交给 Pari，自己保留顶点 $4$（或者也可以交给其他人）。

在第二个样例中，无法同时满足 Pari 和 Arya 的要求。