NP-Hard Problem

## 题目描述 最近，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$，顶点覆盖不能是空的。

Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover problem very interesting. Suppose the graph $ G $ is given. Subset $ A $ of its vertices is called a vertex cover of this graph, if for each edge $ uv $ there is at least one endpoint of it in this set, i.e.  or  (or both). Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover. They have agreed to give you their graph and you need to find two disjoint subsets of its vertices $ A $ and $ B $ , such that both $ A $ and $ B $ are vertex cover or claim it's impossible. Each vertex should be given to no more than one of the friends (or you can even keep it for yourself).

The first line of the input contains two integers $ n $ and $ m $ ( $ 2<=n<=100000 $ , $ 1<=m<=100000 $ ) — the number of vertices and the number of edges in the prize graph, respectively. Each of the next $ m $ lines contains a pair of integers $ u_{i} $ and $ v_{i} $ ( $ 1<=u_{i},v_{i}<=n $ ), denoting an undirected edge between $ u_{i} $ and $ v_{i} $ . It's guaranteed the graph won't contain any self-loops or multiple edges.

If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes). If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integer $ k $ denoting the number of vertices in that vertex cover, and the second line contains $ k $ integers — the indices of vertices. Note that because of $ m>=1 $ , vertex cover cannot be empty.

4 2
1 2
2 3

1
2 
2
1 3 

3 3
1 2
2 3
1 3

-1

In the first sample, you can give the vertex number $ 2 $ to Arya and vertices numbered $ 1 $ and $ 3 $ to Pari and keep vertex number $ 4 $ for yourself (or give it someone, if you wish). In the second sample, there is no way to satisfy both Pari and Arya.