Codeforces Round #360 (Div. 1) A. NP-Hard Problem （二分图）

Codeforces Round #360 (Div. 1) A. NP-Hard Problem （二分图）

A. NP-Hard Problem

time limit per test 2 seconds

memory limit per test 256 megabytes

input standard input

output standard output

Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover

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

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — 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 ui and vi (1  ≤  ui,  vi  ≤  n), denoting an undirected edge between ui and vi. It's guaranteed the graph won't contain any self-loops or multiple edges.

Output

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 kintegers — the indices of vertices. Note that because of m ≥ 1, vertex cover cannot be empty.

Examples

input

4 21 22 3

output

12 21 3

input

3 31 22 31 3

output

-1

Note

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

In the second sample, there is no way to satisfy both Pari and Arya.

题解：多校结束了，写道题压压惊。。。给你一些顶点和边，将顶点分为两组，同一组的任意两个顶点不能相连。输出两组的各点，若不能分，输出-1。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。