显示原始代码
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAX_N = 2e2 + 7;
vector<pii> oe[MAX_N];
vector<int> e[MAX_N];
vector<vector<int> > ans;
int deg[MAX_N], deg_one[MAX_N], mat[MAX_N][MAX_N], dfn[MAX_N], fat[MAX_N], idx[MAX_N][MAX_N], dep[MAX_N],
vis[MAX_N];
int n, m, order;
void gauss() {
for (int i = 1; i <= n; ++i) {
int mpos = i;
for (int j = i; j <= n; ++j) {
if (mat[j][i] > mat[i][i])
mpos = j;
}
if (!mat[mpos][i])
continue;
for (int j = i; j <= n + 1; ++j) swap(mat[i][j], mat[mpos][j]);
for (int j = 1; j <= n; ++j) {
if (i == j || !mat[j][i])
continue;
for (int k = i + 1; k <= n + 1; ++k) {
mat[j][k] ^= mat[i][k];
}
}
}
}
vector<int> a, b, tmp;
void dfs(int u) {
dfn[u] = ++order;
for (int i = 0; i < e[u].size(); ++i) {
int v = e[u][i];
if (v == fat[u])
continue;
if (!dfn[v]) {
fat[v] = u;
dep[v] = dep[u] + 1;
dfs(v);
} else if (dfn[v] < dfn[u]) {
a.clear();
b.clear();
int x = u, y = v;
while (x != y) {
if (dep[x] > dep[y]) {
a.push_back(idx[x][fat[x]]);
x = fat[x];
} else if (dep[x] < dep[y]) {
b.push_back(idx[y][fat[y]]);
y = fat[y];
} else {
a.push_back(idx[x][fat[x]]);
b.push_back(idx[y][fat[y]]);
x = fat[x], y = fat[y];
}
}
tmp.clear();
tmp.push_back(idx[u][v]);
for (int j = 0; j < a.size(); ++j) tmp.push_back(a[j]);
for (int j = b.size() - 1; j >= 0; --j) tmp.push_back(b[j]);
ans.push_back(tmp);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v, t;
scanf("%d%d%d", &u, &v, &t);
oe[u].push_back(pii(v, t));
oe[v].push_back(pii(u, t));
++deg[u];
++deg[v];
deg_one[u] += t, deg_one[v] += t;
++mat[u][v];
++mat[v][u];
mat[u][n + 1] += t;
mat[v][n + 1] += t;
idx[u][v] = idx[v][u] = i;
}
for (int i = 1; i <= n; ++i) {
mat[i][i] = deg[i];
for (int j = 1; j <= n + 1; ++j) {
mat[i][j] = mat[i][j] & 1;
}
}
#ifdef debug
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n + 1; ++j) {
printf("%d ", mat[i][j]);
}
puts("");
}
#endif
vector<int> ps;
bool flag = true;
gauss();
#ifdef debug
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n + 1; ++j) {
printf("%d ", mat[i][j]);
}
puts("");
}
#endif
for (int i = 1; i <= n; ++i) {
if (mat[i][n + 1] && !mat[i][i]) {
flag = false;
break;
} else {
if (mat[i][i] && mat[i][n + 1])
ps.push_back(i), vis[i] = true;
}
}
if (flag) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < oe[i].size(); ++j) {
int v = oe[i][j].first;
if (vis[i] != vis[v])
oe[i][j].second ^= 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < oe[i].size(); ++j) {
if (oe[i][j].second) {
e[i].push_back(oe[i][j].first);
}
}
}
#ifdef debug
for (int i = 1; i <= n; ++i) {
printf("%d: ", i);
for (int j = 0; j < e[i].size(); ++j) printf("%d ", e[i][j]);
puts("");
}
#endif
for (int i = 1; i <= n; ++i) {
if (!dfn[i])
dfs(i);
}
printf("%d\n", (ps.size() > 0) + ans.size());
if (ps.size()) {
printf("2 %d", ps.size());
for (int i = 0; i < ps.size(); ++i) printf(" %d", ps[i]);
puts("");
}
for (int i = 0; i < ans.size(); ++i) {
printf("1 %d", ans[i].size());
for (auto u : ans[i]) {
printf(" %d", u);
}
puts("");
}
} else {
puts("-1");
}
return 0;
}