405039 - 信息共享

小光需要把一条信息传送给千里之遥的n(2≤n≤200)个魔法师,为了节省魔法力,他只需要把信息传送给少数的几个魔法师,然后由魔法师们相互传递该信息即可。但魔法师们的关系有好有坏,例如A愿意传递信息给B,B不愿意传递信息给C,因此他们组成了一个个小圈子,在小圈子里的所有魔法师相互之间可以直接或间接地传递信息,不同的圈子不能互相传递信息。换句话说,如果A愿意传递信息给B,而B无法直接或间接把信息传递给A,则A和B不属于同一个小圈子,极端情况下,一个人组成一个小圈子。现给出魔法师们的关系,问小光需要传送信息给几个小圈子的人才可以保证所有的魔法师都能分享到该信息?

输入

第一行为一个整数n,随后n行,每行数字个数不等,依次表示每个魔法师愿意分享信息给其他魔法师的编号,每行以0结束。 如果某个魔法师不愿意分享信息给任何人,则相应行只有1个0。

输出

一个正整数,表示最多要传递的信息次数。

样例

输入

6
2 3 0
4 0
4 5 0
1 6 0
6 0
0

输出

3
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题