显示原始代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 320;
vector<pii> G[MAXN];
vector<vector<int> > op1, op2;
bitset<MAXN> base[MAXN], bs[MAXN], deg, from[MAXN];
int cho[MAXN * MAXN], dfn[MAXN], dfsClock;
pii fa[MAXN];
void dfs(int u, int fath) {
dfn[u] = ++dfsClock;
for (auto [g, id] : G[u])
if (g != fath) {
if (!dfn[g]) {
fa[g] = { u, id };
dfs(g, u);
} else if (dfn[g] < dfn[u] && cho[id]) {
vector<int> todo;
todo.push_back(id), cho[id] ^= 1;
int p = u;
while (p != g) {
auto [f, fid] = fa[p];
p = f, todo.push_back(fid), cho[fid] ^= 1;
}
op1.push_back(todo);
}
}
}
void solve() {
int n, m;
scanf("%d%d", &n, &m);
rep(i, m) {
static int x, y;
scanf("%d%d%d", &x, &y, &cho[i]);
G[x].emplace_back(y, i);
G[y].emplace_back(x, i);
bs[x].flip(y), bs[y].flip(x);
bs[x].flip(x), bs[y].flip(y);
if (cho[i])
deg.flip(x), deg.flip(y);
}
rep(i, n) {
bitset<MAXN> me;
me[i] = true;
for (int j = n; j >= 0; --j)
if (bs[i][j]) {
if (!base[j][j]) {
base[j] = bs[i], from[j] = me;
break;
}
bs[i] ^= base[j], me ^= from[j];
}
}
bool solved = true;
bitset<MAXN> me;
for (int i = n; i >= 0; --i)
if (deg[i]) {
if (!base[i][i]) {
solved = false;
break;
}
deg ^= base[i], me ^= from[i];
}
if (!solved) {
puts("-1");
return;
}
vector<pair<int, vector<int> > > ans;
vector<int> red;
rep(i, n) if (me[i]) {
red.push_back(i);
for (auto [g, id] : G[i])
if (!me[g])
cho[id] ^= 1;
}
if (red.size())
op2.push_back(red);
rep(i, n) if (!dfn[i]) dfs(i, -1);
rep(i, m) assert(!cho[i]);
cout << op1.size() + op2.size() << '\n';
for (auto v : op2) {
cout << "2 " << v.size();
for (auto g : v) cout << ' ' << g;
cout << '\n';
}
for (auto v : op1) {
cout << "1 " << v.size();
for (auto g : v) cout << ' ' << g;
cout << '\n';
}
}
int main() {
solve();
return 0;
}