这题是一道关于图论的题目。

为了让大家容易理解题意，题目就没有什么背景啊、故事啊什么的。

就直接奔入主题吧！

有向无环图G(V,E)的一个路径覆盖是指一个路径集合P，满足图中的每点属于且仅属于集合中的一条路径。

由于出题者不知道如何上传图片，就用数字来解释吧。

考虑一个有5个顶点的有向无环图，有6条路径为

1->3

2->3

2->5

3->4

3->5

4->5

那么最少路径覆盖|P|min=2，

有三种方案：

A.{1->3->4->5, 2}

B.{2->3->4->5, 1}

C.{1->3->4, 2->5}

现在，聪明的你应该知道了你的任务就是：

给你一个有向无环图G=(V,E)，求一个包含路径数最少的路径覆盖P。

输入测试数据有多笔。

每组测资的第一行是两个数n和m，分别代表有向无环图的节点数和接下来的信息数。

接下来m行，每行都是一对数x和y，表示存在一条路使得x可以不通过其他节点而直接到达y，即x->y。

当 x=y=0 时，代表输入结束，不必对这笔输入输出任何字符。

5 6
1 3
2 3
2 5
3 4
3 5
4 5
0 0

2

由于为了保证有向图无环且无重边，所以测资很难生。

所以测资保证有

1<=n<=100

0<=m<=n*(n+1)/2

且有向图中一定没有环，也没有重边。

但是还希望大家将程序写得有效率一点，让它可以过掉n=1000的测资吧！

这对大家一定是一个挑战！

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

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

分析：

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

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

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

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