样例 2 直接输出了一万个 10。交上去 30pts。。好像是存父亲的时候爆了,有很多重边。
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e6 + 10;
ll n, m, cnt = 1, dep, _dep;
int dfn[N], cut[N], _dfn[N], low[N], f[N];
bool cut1[N], on_tree[N];
ull w[N];
gp_hash_table<ull, bool> st;
gp_hash_table<ull, int> mp;
vector<int> vec[N], g[N];
vector<vector<int>> ans;
inline ll read() {
ll x = 0, m = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') m = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * m;
}
inline void write(ll x) {
if(x < 0) {
putchar('-');
write(-x);
return;
}
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
mt19937 rnd(time(NULL));
inline ull get_rnd() {
return rnd() | 1ull * rnd() << 32;
}
inline void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ dep;
for(int i = 0; i < vec[u].size(); ++ i) {
int v = vec[u][i];
if(g[u][i] == (fa ^ 1)) continue;
if(!dfn[v]) {
tarjan(v, g[u][i]);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[v]) cut[g[u][i]] = cut[g[u][i] ^ 1] = 1;
} else low[u] = min(low[u], dfn[v]);
}
}
inline void dfs3(int u, int vv, vector<int> &now) {
now.push_back(u);
for(int i = 0; i < vec[u].size(); ++ i) {
int v = vec[u][i];
if(cut[g[u][i]] || cut1[g[u][i]] || !on_tree[g[u][i]] || v == vv) continue;
dfs3(v, vv, now);
}
}
int aa;
inline void dfs2(int u, int fa) {
// if(++ aa < 20) for(int i = 0; i < vec[10].size(); ++ i) cout << vec[10][i] << endl;
for(int i = 0; i < vec[u].size(); ++ i) {
int v = vec[u][i];
if(cut[g[u][i]] || cut1[g[u][i]] || !on_tree[g[u][i]]) continue;
dfs2(v, g[u][i]);
}
if(mp.find(w[u]) != mp.end()) {
int v = mp[w[u]];
vector<int> tmp;
dfs3(u, v, tmp);
ans.push_back(tmp);
vec[f[u]].push_back(v), g[f[u]].push_back(++ cnt);
on_tree[fa] = 0, on_tree[cnt] = 1, f[v] = f[u];
mp[w[u]] = v;
} else mp[w[u]] = u;
}
inline void dfs1(int u, int fa) {
_dfn[u] = ++ _dep;
for(int i = 0; i < vec[u].size(); ++ i) {
int v = vec[u][i];
if(g[u][i] == (fa ^ 1) || cut[g[u][i]]) continue;
if(_dfn[v]) {
if(_dfn[v] > _dfn[u]) continue;
ull val = get_rnd();
w[u] ^= val, w[v] ^= val;
st[val] = 1;
} else {
on_tree[g[u][i]] = 1, f[v] = u;
dfs1(v, g[u][i]);
w[u] ^= w[v];
}
}
if(st.find(w[u]) != st.end()) cut1[fa] = cut1[fa ^ 1] = 1;
if(cut1[fa] || !fa) {
mp.clear();
dfs2(u, 0);
vector<int> tmp;
dfs3(u, 0, tmp);
ans.push_back(tmp);
}
}
signed main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= m; ++ i) {
int u = read(), v = read();
vec[u].push_back(v), vec[v].push_back(u);
g[u].push_back(++ cnt), g[v].push_back(++ cnt);
}
for(int i = 1; i <= n; ++ i) if(!dfn[i]) tarjan(i, 0);
for(int i = 1; i <= n; ++ i) if(!_dfn[i]) dfs1(i, 0);
for(vector<int> &v : ans) sort(v.begin(), v.end());
sort(ans.begin(), ans.end());
write(ans.size()), putchar('\n');
for(vector<int> v : ans) {
for(int x : v) write(x), putchar(' ');
putchar('\n');
}
return 0;
}