题目描述

最近，Pari和Arya对NP-Hard问题进行了一些研究，他们发现最小顶点覆盖问题非常有趣。

对于给定的图$G$，其顶点集合的子集$A$被称为此图的一个顶点覆盖，当且仅当对于图中的每条边$uv$，其都有至少一个顶点在此子集中，即$u \in A$或$v \in A$（或二者皆符合）

Pari和Arya在一场团队比赛中赢得了一个很棒的无向图作为奖励。现在他们要把它分成两份，但他们两个都想让自己的那份是这个图的一个顶点覆盖。

他们同意将他们的图给你，而你需要找到此图的两个不相交的顶点集合$A$和$B$并令$A$和$B$都是此图的一个顶点覆盖，或说明这是不可能的。图的每个顶点都应该被给予两人中的至多一人（当然你也可以自己留着）。

输入格式

输入的第一行包含两个整数$n$和$m$（$2 \leq n \leq 100000$ , $1 \leq m \leq 100000$）,二者分别为所给图的顶点数和边数。

接下来的$m$行每行包含两个整数$u_i$和$v_i$（$1 \leq u_i,v_i \leq n$），表示一条$u_i$和$v_i$之间的无向边。保证图中不存在自环和重边。

输出格式

如果不可能按Pari和Arya所期望的方式分割这个图，输出"-1"（不含引号）。

如果存在符合要求的两个顶点覆盖，输出它们的描述。每个描述必须包含两行：第一行包含一个整数$k$，代表这个顶点覆盖中的顶点数；第二行包含$k$个整数，为其中顶点的编号。注意：因为$m \geq 1$，顶点覆盖不能是空的。

4 2
1 2
2 3

1
2 
2
1 3

3 3
1 2
2 3
1 3

-1