← 返回题目列表

Codeforces · 687/A

A. NP 难题

中文机器翻译题面 查看原题

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

假设给出图G。其顶点的子集 A 称为该图的顶点覆盖,如果对于每条边 uv 在该集合中至少有一个端点,即 $$u \in A$$ 或 $$v \in A$$ (或两者)。

Pari 和 Arya 在团队竞赛中赢得了一个很棒的无向图作为奖励。现在他们必须将其分成两部分,但他们都希望自己的图部分成为顶点覆盖。

他们同意向您提供他们的图,您需要找到其顶点 A 和 B 的两个不相交子集,使得 A 和 B 都是顶点覆盖或声称这是不可能的。每个顶点只能给一位朋友(或者您甚至可以自己保留)。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000)——分别是奖品图中的顶点数和边数。

接下来的 m 行中的每一行都包含一对整数 ui 和 vi (1 ≤ ui, vi ≤ n),表示 ui 和 vi 之间的无向边。保证图形不会包含任何自环或多重边。

输出

如果无法按照 Pari 和 Arya 的预期拆分图表,请打印“-1”(不带引号)。

如果有两个不相交的顶点集,使得两个集合都是顶点覆盖,则打印它们的描述。每个描述必须包含两行。第一行包含一个整数 k,表示该顶点覆盖中的顶点数,第二行包含 k 个整数 — 顶点的索引。请注意,由于 m ≥ 1,顶点覆盖不能为空。

示例

输入 #1

4 2
1 2
2 3

输出 #1

1
2
2
1 3

输入 #2

3 3
1 2
2 3
1 3

输出 #2

-1

注意

在第一个示例中,您可以将顶点编号 2 指定给 Arya,将顶点编号 1 和 3 指定给 Pari,并将顶点编号 4 保留给自己(如果您愿意,也可以将其交给其他人)。

在第二个示例中,无法同时满足 Pari 和 Arya。