P0546

清理雪道

清理雪道

滑雪场坐落在 FJ 省西北部的若干座山上。

从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。

由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。

输入格式

第一行包含一个整数 nn,代表滑雪场的地点的数量。

接下来的 nn 行描述从 1∼n1\sim n 号地点出发的斜坡:第 ii 行的第一个数为 mim_i,表示从地点 ii 出发的斜坡数目;后面共有 mim_i 个整数,由空格隔开,每个整数 aija_{ij} 互不相同,代表从地点 ii 下降到地点 aija_{ij} 的斜坡。

保证每个地点至少有一个斜坡与之相连。

输出格式

输出一行一个整数 kk,表示直升飞机的最少飞行次数。

样例输入

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

样例输出

4

数据范围

  • 2≤n≤1002\le n\le 100;
  • 0≤mi<n0\le m_i<n。

来源与许可

本题为「清理雪道」,题面与测试数据整理自 BZOJ 2502。

样例 1

输入

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

输出

4