题目描述

给定有向图$\red {G=(V,E)}$。设$\red {P}$ 是$\red {G}$ 的一个简单路（顶点不相交）的集合。如果$\red {V}$ 中每个 顶点恰好在$\red {P}$ 的一条路上，则称$\red {P}$是$\red {G}$ 的一个路径覆盖。$\red {P}$ 中路径可以从$\red {V}$ 的任何一个顶 点开始，长度也是任意的，特别地，可以为$\red {0}$。$\red {G}$ 的最小路径覆盖是$\red {G}$ 的所含路径条数最少 的路径覆盖。 设计一个有效算法求一个有向无环图$\red {G}$ 的最小路径覆盖。 提示：设$\red {V=\{1，2，... ，n\}}$，构造网络$\red {G1=(V1,E1)}$如下：

每条边的容量均为$\red {1}$。求网络$\red {G1}$的$\red {（ x_0 , y_0 ）}$最大流。 编程任务： 对于给定的有向无环图$\red {G}$，编程找出$\red {G}$的一个最小路径覆盖。

输入格式

由文件$\red {input.txt}$提供输入数据。文件第$\red {1}$ 行有$\red {2}$个正整数$\red {n}$和$\red {m}$。$\red {n}$是给定有向无环图 $\red {G}$ 的顶点数，$\red {m}$是$\red {G}$ 的边数。接下来的$\red {m}$行，每行有$\red {2}$ 个正整数$\red {i}$和$\red {j}$，表示一条有向边$\red {(i,j)}$。

输出格式

程序运行结束时，将最小路径覆盖输出到文件$\red {output.txt}$ 中。从第$\red {1}$ 行开始，每行输出 一条路径。文件的最后一行是最少路径数。

样例

输入样例

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