# 問題概要
無向グラフ (頂点数 n, 枝数 m) が与えられる。
このグラフの頂点集合を互いに disjoint な 2 つの集合 A, B に分割して、
A, B がともに vertex cover となっているようにせよ。
そのようなものが存在しなければ -1 をリターンせよ。
# 制約
2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000
# 解法
二部グラフとなっているかどうかを判定する。
なっていれば、それぞれの頂点集合を出力する。
# コード
```cpp
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 210000;
vector
int seen[MAX];
vector
bool cannot = false;
void dfs(int v, int color) { // 1: left, 2: right
seen[v] = color;
if (color == 1) Left.push_back(v);
if (color == 2) Right.push_back(v);
int next_color = 3 - color;
for (int i = 0; i < G[v].size(); ++i) {
int to = G[v][i];
if (seen[to]) {
if (seen[to] != next_color) {
cannot = true;
}
}
else {
dfs(to, next_color);
}
}
}
int main() {
int n, m;
while (cin >> n >> m) {
for (int i = 0; i < MAX; ++i) G[i].clear();
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
G[a].push_back(b);
G[b].push_back(a);
}
for (int i = 0; i < MAX; ++i) seen[i] = 0;
Left.clear(); Right.clear();
cannot = false;
for (int v = 0; v < n; ++v) {
if (seen[v]) continue;
dfs(v, 1);
}
if (cannot) cout << -1 << endl;
else {
cout << Left.size()<< endl;
for (int i = 0; i < Left.size(); ++i) {
cout << Left[i] + 1;
if (i != (int)Left.size() - 1) cout << " ";
}
cout << endl;
cout << Right.size()<< endl;
for (int i = 0; i < Right.size(); ++i) {
cout << Right[i] + 1;
if (i != (int)Right.size() - 1) cout << " ";
}
cout << endl;
}
}
}
```
