CF687A.NP-Hard Problem

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

最近，帕里（Pari）和阿丽亚（Arya）研究了一些关于 NP-Hard 问题的内容，发现最小顶点覆盖问题非常有趣。

假设给定一个图 $ G $。其顶点的一个子集 $ A $ 被称为该图的一个顶点覆盖，当且仅当对图中每一条边 $ uv $，其至少有一个端点属于该集合，即满足 或 （或两者同时成立）。

帕里和阿丽亚在一次团队竞赛中赢得了一张非常棒的无向图作为奖品。现在他们需要将这张图分成两部分，但两人都希望各自分得的部分构成一个顶点覆盖。

他们已达成一致：将这张图交给你，并请你找出两个互不相交的顶点子集 $ A $ 和 $ B $，使得 $ A $ 和 $ B $ 均为顶点覆盖；若不存在这样的划分，则需声明其不可能。每个顶点至多只能分配给其中一位朋友（你甚至可以自己保留某些顶点）。

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

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

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

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.

如果无法按照帕里和阿莉亚的期望将图分割，则输出“-1”（不带引号）。

如果存在两个互不相交的顶点集合，且这两个集合均为顶点覆盖，则输出它们的描述。每个描述必须包含两行：第一行是一个整数 $k$，表示该顶点覆盖中顶点的数量；第二行是 $k$ 个整数——这些顶点的下标。注意，由于 $m \geq 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.

在第一个样例中，你可以将编号为 2 的顶点分给 Arya，将编号为 1 和 3 的顶点分给 Pari，并将编号为 4 的顶点留给自己（或者随意分给其他人）。

在第二个样例中，不存在一种分配方式能同时满足 Pari 和 Arya。