显示原始代码
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 205
using namespace std;
struct edge {
int x, id;
edge(int nx = 0, int nid = 0) {
x = nx;
id = nid;
}
} h;
int is = 0, n, m, x, y, t, dfn[MAX], ff[MAX], cnt = 0, tot = 0, pre[MAX], d[MAX], kr[MAX], mat[MAX][MAX],
ans[MAX], b[MAX], gr[MAX][MAX];
vector<edge> s[MAX];
vector<int> opt[MAX * MAX / 2];
void Swap(int u, int v) {
for (int i = 1; i <= n; i++) swap(mat[u][i], mat[v][i]);
swap(b[u], b[v]);
}
void eli(int u, int v) {
for (int i = 1; i <= n; i++) mat[v][i] ^= mat[u][i];
b[v] ^= b[u];
}
void dfs(int p, int f) {
dfn[p] = ++cnt;
ff[p] = f;
edge v;
int tmp;
for (int i = 0; i < (int)s[p].size(); i++) {
v = s[p][i];
if (dfn[v.x] > dfn[p])
continue;
if (dfn[v.x]) {
if (v.x == f)
continue;
if (gr[v.x][p]) {
tot++;
opt[tot].push_back(v.id);
tmp = p;
while (tmp != v.x) {
opt[tot].push_back(pre[tmp]);
tmp = ff[tmp];
}
}
continue;
}
pre[v.x] = v.id;
dfs(v.x, p);
}
}
int main() {
memset(ans, -1, sizeof(ans));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &t);
gr[x][y] = gr[y][x] = t;
s[x].push_back(edge(y, i));
s[y].push_back(edge(x, i));
d[x]++;
d[y]++;
mat[x][y] = mat[y][x] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (gr[i][j])
b[i] ^= 1;
if (d[i] & 1)
mat[i][i] = 1;
}
int rk = 0, kp;
for (int i = 1; i <= n; i++) {
kp = 0;
for (int j = rk + 1; j <= n; j++) {
if (mat[j][i]) {
kp = j;
break;
}
}
if (kp == 0)
continue;
rk++;
kr[rk] = i;
Swap(rk, kp);
for (int j = 1; j <= n; j++) {
if (j == rk)
continue;
if (mat[j][i])
eli(rk, j);
}
}
for (int i = rk + 1; i <= n; i++) {
if (b[i]) {
printf("-1\n");
return 0;
}
}
for (int i = rk; i > 0; i--) {
for (int j = n; j > kr[i]; j--) {
if (ans[j] != -1)
b[i] ^= ans[j] * mat[i][j];
else
ans[j] = 0;
}
if (b[i])
ans[kr[i]] = 1, is++;
else
ans[kr[i]] = 0;
}
for (int i = 1; i <= n; i++) {
if (ans[i]) {
for (int j = 0; j < (int)s[i].size(); j++) {
h = s[i][j];
gr[h.x][i] ^= 1;
gr[i][h.x] ^= 1;
}
}
}
dfs(1, 0);
printf("%d\n", (is > 0) + tot);
if (is) {
printf("2 %d ", is);
for (int i = 1; i <= n; i++)
if (ans[i] == 1)
printf("%d ", i);
printf("\n");
}
for (int i = 1; i <= tot; i++) {
printf("1 %d ", (int)opt[i].size());
for (int j = 0; j < (int)opt[i].size(); j++) printf("%d ", opt[i][j]);
printf("\n");
}
return 0;
}