说几句与这题无关的闲话。
学校好傻逼啊为什么要在学竞赛的时候突然把我们抓回去上文化。
说回正题。
这题要求最小路径覆盖。最小路径覆盖的一个经典解法就是拆点，建二分图。
输出路径的话在残量网络上找流完的边然后随便搞搞即可。
#include <bits/stdc++.h>
#define llong long long
#define N 155
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}bitset<N> G[N];
vector<int> g[N];
int n, m;int to[N*N], siz[N*N], nxt[N*N], head[N<<1], gsiz = 1;
#define mkarc(u,v,w) (++gsiz, to[gsiz]=v, siz[gsiz]=w, nxt[gsiz]=head[u], head[u]=gsiz)
int cur[N<<1], lev[N<<1];int que[N<<1], he, ta;
inline bool bfs(){for(int i = 1; i <= n*2+2; ++i) lev[i] = 0, cur[i] = head[i];que[he = ta = 1] = n*2+1, lev[n*2+1] = 1;while(he <= ta){int u = que[he++];if(u == n*2+2) return true;for(int i = head[u]; i; i = nxt[i]){int v = to[i];if(lev[v] || !siz[i]) continue;lev[v] = lev[u]+1;que[++ta] = v;}}return false;
}
inline int dfs(int u, int f){if(u == n*2+2) return f;int res = 0;for(int &i = cur[u]; i; i = nxt[i]){int v = to[i];if(lev[v] != lev[u]+1 || !siz[i]) continue;int d = dfs(v, min(f, siz[i]));if(!d) lev[v] = -1;siz[i] -= d, f -= d;siz[i^1] += d, res += d;if(!f) break;}return res;
}
inline int dinic(){int res = 0;while(bfs()) res += dfs(n*2+1, 1e9+7);return res;
}int nxt2[N], deg[N];int main(){freopen("in.txt", "r", stdin);read(n, m);for(int i = 1; i <= m; ++i){int u, v; read(u, v);g[u].push_back(v);G[u][v] = true;}
// for(int k = 1; k <= n; ++k)
// for(int i = 1; i <= n; ++i)
// if(G[i][k]) G[i] |= G[k];for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(G[i][j] && i != j) mkarc(i, j+n, 1), mkarc(j+n, i, 0);for(int i = 1; i <= n; ++i){mkarc(n*2+1, i, 1), mkarc(i, n*2+1, 0);mkarc(i+n, n*2+2, 1), mkarc(n*2+2, i+n, 0);}int ans = n-dinic();for(int u = 1; u <= n; ++u)for(int i = head[u]; i; i = nxt[i])if(!siz[i] && to[i] <= n*2) nxt2[u] = to[i]-n, ++deg[to[i]-n];for(int i = 1; i <= n; ++i){if(deg[i]) continue;for(int j = i; j; j = nxt2[j])printf("%d ", j);printf("\n");}printf("%d", ans);return 0;
}