题目描述

你负责一个团队来检查一个新的滑雪度假村。滑雪度假胜地坐落在几座山上，由许多坡道组成。

坡道之间相互连接，分叉和汇聚。滑雪度假村的地图可表示为一个无环有向图。

图的节点代表滑雪度假胜地中的不同点，图的边表示连通这些点的坡道，边的方向是向下的。

你的团队必须检查滑雪度假胜地的每一条坡道。这个度假村的滑道还没有开放，但是你们有一架直升飞机。

在一次飞行中，直升机可以把一个人投放到度假村的任何一个点上。从投放点出发，这个人可以滑下坡道，检查每个坡道。重复检查同一坡道是可以接受的，但你必须最小化直升机的使用。

因此，你必须弄清楚如何以最少的直升机飞行次数来检查所有的坡道。

简易题面

给张有向无环图，问至少多少条路径能够覆盖所有的边（可以重复）。

输入格式

输入文件的第一行包含一个整数 $n$，表示滑雪度假村中的点数。

接下来的 $n$ 行描述滑雪度假村的每个点，编号从 $1$ 到 $n$。

每行以一个整数 $m_i$ 开始（对于$i$从 $1$ 到 $n$ 有 $0 \leq m_i < n$），后跟 $m_i$个用空格分隔的整数 $a_{i,j}$。

对于每个 $i$ 和每个 $a_{i,j}$ 都是不同的，它们分别表示从点 $i$ 到 $a_{i,j}$ 的向下的坡度。每个度假村的点至少有一条与其相连的坡度。

输出格式

在输出文件的第一行写入一个整数 $k$，表示检查所有坡道所需的最小直升机飞行次数。

然后写入 $k$ 行，描述每次直升机飞行的检查路线。每个路线应从 $1$ 到 $n$ 的单个整数开始，表示直升机飞行的投放点的编号，后跟按照检查的坡道相应的顺序访问的点编号。

每行上的数字应由空格分隔。您可以以任何顺序编写路线。

8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0

4

数据规模与约定

对于 $100\%$ 的数据，$2 \leq n \leq 100$，$1 \leq a_{i,j} \leq n$。

题目来源

Neerc2009