Description

Given a directed graph $G=(V,E)$. Let $P$ be a set of simple paths (vertex-disjoint) in $G$. If every vertex in $V$ appears in exactly one path in $P$, then $P$ is a path cover of $G$. Paths in $P$ can start at any vertex in $V$, and their lengths are arbitrary; in particular, the length can be $0$. The minimum path cover of $G$ is a path cover with the fewest number of paths. Design an efficient algorithm to find a minimum path cover of a DAG (directed acyclic graph) $G$.

Input Format

The first line contains two positive integers $n$ and $m$. Here $n$ is the number of vertices of the given DAG (directed acyclic graph) $G$, and $m$ is the number of edges of $G$. The next $m$ lines each contain two positive integers $i$ and $j$, representing a directed edge $(i, j)$.

Output Format

Starting from the first line, output one path per line. The last line of the file is the minimum number of paths.

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

Hint

Constraints: For $100\%$ of the testdata, $1 \leq n \leq 150$, $1 \leq m \leq 6000$.

SPJ provided by @FlierKing.

Translated by ChatGPT 5