最近,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。