#6002. 「网络流 24 题」最小路径覆盖

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

给定有向图 G=(V,E)G = (V, E)。设 PPGG 的一个简单路(顶点不相交)的集合。如果 VV 中每个顶点恰好在 PP 的一条路上,则称 PPGG 的一个路径覆盖。PP 中路径可以从 VV 的任何一个顶点开始,长度也是任意的,特别地,可以为 00GG 的最小路径覆盖是 GG 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 GG 的最小路径覆盖。

输入格式

11 行有 22 个正整数 nnmmnn 是给定有向无环图 GG 的顶点数,mmGG 的边数。
接下来的 mm 行,每行有 22 个正整数 uuvv,表示一条有向边 (i,j)(i, j)

输出格式

从第 11 行开始,每行输出一条路径。
文件的最后一行是最少路径数。

样例

样例输入

11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11

样例输出

1 4 7 10 11
2 5 8
3 6 9
3

数据范围与提示

1n200,1m60001 \leq n \leq 200, 1 \leq m \leq 6000