NP-Hard Problem (二分图着色)

NP-Hard问题

每个测试用例的时间限制

2秒

每个测试用例的内存限制

256兆字节

输入方式

标准输入

输出方式

标准输出

最近，Pari和Arya对NP-Hard问题进行了研究，并发现最小顶点覆盖问题非常有趣。

假设给定图G。如果对于每条边uv，该集合中至少包含其一个端点，即u属于A或v属于A（或两者都属于），则该图的顶点子集A被称为顶点覆盖。

Pari和Arya在团队竞赛中赢得了一个出色的无向图作为奖品。现在他们需要将这个图分成两部分，但他们都希望各自获得的部分能够构成一个顶点覆盖。

他们达成一致，将他们的图交给你，并要求你找到两个互不重叠的顶点子集A和B，使得这两个子集均为顶点覆盖；或者声明这是不可能的。每个顶点只能分配给其中一位朋友（甚至可以自己保留）。

输入

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

接下来的m行每行包含两个整数u_i和v_i（1 ≤ u_i, v_i ≤ n），表示u_i与v_i之间有一条无向边。保证该图不包含自环或多重边。

输出

如果无法按照Pari和Arya的要求将图进行分割，请输出“-1”（不带引号）。

如果存在两个互不重叠的顶点集合，且这两个集合均为顶点覆盖，请输出它们的描述。每个描述必须包含两