题意：
有向无环图中，需要多少条简单路可以覆盖整个图。

建模：
构造二分图。把原图的每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图的边(i, i)，连接(Xi, Yj)，值为1，然后把二分图最大匹配模型转化为网络留模型，求最大流。

分析：

对于一个路径覆盖，有如下性质：

1、每个顶点属于且只属于一个路径。
2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。

所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。

注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <memory.h>

using namespace std;

const int MAXN = 100;
const int MAXM = MAXN*MAXN;
const int INF  = 0x7FFFFFF;

typedef struct edge{
    edge *next, *op;
    int t,c;
}edge;

edge ES[MAXM], *V[MAXN], *P[MAXN], *Stae[MAXN];
int level[MAXN], Stap[MAXN];
int M, N, S, T, EC, Ans, Maxflow;

ifstream fin("path.in");
ofstream fout("path.out");

inline void addedge(int a, int b, int c){
    ES[++EC].next=V[a], V[a]=ES+EC, V[a]->t=b, V[a]->c=c;
    ES[++EC].next=V[b], V[b]=ES+EC, V[b]->t=a, V[b]->c=0;
    V[a]->op=V[b], V[b]->op=V[a];
}

bool Dinic_Level(){
    int head,tail,i,j;
    Stap[head=tail=0]=S;
    memset(level,-1,sizeof(level));
    level[S]=0;
    while (head<=tail){
        i=Stap[head++];
        for (edge *e=V[i];e;e=e->next){
            j=e->t;
            if (e->c && level[j]==-1){
                level[j] = level[i]+1;
                if (j==T)
                    return true;
                Stap[++tail] = j;
            }
        }
    }
    return false;
}

int match[MAXN+MAXN];
void Dinic_Augment(){
    int i,j,delta,Stop;

    memcpy(P, V, sizeof(edge*)*MAXN);

    Stap[Stop=1]=S;
    while (Stop){
        i=Stap[Stop];
        if (i!=T){
            for (;P[i];P[i]=P[i]->next)
                if (P[i]->c && level[i] + 1 == level[j=P[i]->t])
                    break;
            if (P[i]){
                Stap[++Stop] = j;
                Stae[Stop] = P[i];
            }else
                Stop--,level[i]=-1;
        }else{
            delta = INF;
            for (i=Stop;i>=2;i--)
                if (Stae[i]->c < delta)
                    delta = Stae[i]->c;
            Maxflow += delta;
            for (i=Stop;i>=2;i--){
                Stae[i]->c -= delta;
                Stae[i]->op->c += delta;
                if (Stae[i]->c==0)
                    Stop = i-1;
            }
            match[Stae[2]->t] = Stae[3]->t;
        }
    }
}

void Dinic(){
    while (Dinic_Level())
        Dinic_Augment();
}

void input(){
    int a,b,i;
    fin>>N>>M;
    S=0, T=N+N+1;
    for(i=1; i<=N; ++i){
        addedge(S, 2*i-1,1);
        addedge(2*i, T, 1);
    }

    for(i=1; i<=M; ++i){
        fin>>a>>b;
        addedge(2*a-1, 2*b, INF);
    }
}

bool visited[MAXN];
void dfs(int k){
    fout<<(k+1)/2<<" ";
    if(match[k]&&!visited[k]){
        visited[k]=true;
        dfs(match[k]-1);
    }
}

void output(){
    int c = N+N;
    for(int i=1; i<c; i+=2){
        if(match[i]&&!visited[i]){
            dfs(i);
            fout<<endl;
        }
    }
    fout<<N-Maxflow<<endl;
}

int main(){
    input();
    Dinic();
    output();
    return 0;
}