|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 1e5 + 10, M = 2e6 + 10;
|
|
|
|
|
|
// 标准错误答案@！
|
|
|
// #2162. 「POI2011 R2 Day1」垃圾运输 Garbage
|
|
|
// https://loj.ac/s/1857935
|
|
|
|
|
|
// 并查集
|
|
|
int p[N], sz[N];
|
|
|
int find(int x) {
|
|
|
if (x == p[x]) return x;
|
|
|
return p[x] = find(p[x]);
|
|
|
}
|
|
|
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
int d[N];
|
|
|
|
|
|
vector<int> res[N];
|
|
|
int rl;
|
|
|
|
|
|
int st[M];
|
|
|
|
|
|
void dfs(int u) {
|
|
|
for (int i = h[u]; ~i; i = h[u]) {
|
|
|
h[u] = ne[i];
|
|
|
if (st[i]) continue;
|
|
|
st[i] = st[i ^ 1] = 1;
|
|
|
int v = e[i];
|
|
|
dfs(v);
|
|
|
cout << u << " ";
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("P3520.in", "r", stdin);
|
|
|
#endif
|
|
|
memset(h, -1, sizeof h);
|
|
|
int n, m;
|
|
|
scanf("%d %d", &n, &m);
|
|
|
|
|
|
// 初始化并查集
|
|
|
for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
|
|
|
|
|
|
int a, b, s, t;
|
|
|
while (m--) {
|
|
|
scanf("%d %d %d %d", &a, &b, &s, &t);
|
|
|
if (s ^ t) {
|
|
|
add(a, b), add(b, a);
|
|
|
d[a]++, d[b]++;
|
|
|
// 并查集
|
|
|
int pa = find(a), pb = find(b);
|
|
|
if (pa != pb) {
|
|
|
p[pb] = pa;
|
|
|
sz[pa] += sz[pb]; // 维护家庭人员数量
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
if (d[i] % 2) {
|
|
|
puts("NIE");
|
|
|
exit(0);
|
|
|
}
|
|
|
|
|
|
// 肯定是存在欧拉回路,现在是几个环呢？可以用并查集提前处理出来
|
|
|
|
|
|
// 从头到尾，看一下有多少个家庭，就是有多少个环
|
|
|
int cnt = 0;
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
if (d[i] && i == p[i]) cnt++;
|
|
|
cout << cnt << endl;
|
|
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
if (d[i] && i == p[i]) {
|
|
|
cout << sz[i] << " " << i << " ";
|
|
|
dfs(i);
|
|
|
cout << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
} |
