#753. 信息传递

信息传递

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

n \red{n} 个同学(编号为 1 \red{1} n \red{n} )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i \red{i } 的同学的信息传递对象是编号为 Ti\red{ T_i} 的同学。游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?

输入格式

输入共 2 \red{2} 行。

1 \red{1} 行包含 1 \red{1 } 个正整数 n\red{ n} ,表示 n \red{n } 个人。

2 \red{2 } 行包含 n\red{ n } 个用空格隔开的正整数 T1,T2,,Tn \red{T_1, T_2, \ldots ,T_n },其中第 Ti \red{T_i } 个整数表示编号为 i \red{i} 的同学的信息传递对象是编号为 Ti \red{T_i} 的同学,Tin \red{T_i \leq n }Tii \red{T_i \neq i}

数据保证游戏一定会结束。

输出格式

输出共 1 \red{1 } 行,包含 1 \red{1 } 个整数,表示游戏一共可以进行多少轮。

样例

输入样例

5
2 4 2 3 1

输出样例

3

image

游戏的流程如图所示。当进行完第3轮游戏后,4号玩家会听到2号玩家告诉他自己的生日,所以答案为3。当然,第3轮游戏后,2号玩家、3号玩家都能从自己的消息来源得知自己的生日,同样符合游戏结束的条件。

提示

对于 30%\red{ 30\% } 的数据,n200 \red{n \leq 200 }

对于 60% \red{60\%} 的数据,n2500 \red{n \leq 2500}

对于 100%\red{ 100\% } 的数据,n200000\red{ n \leq 200000}

数据结构3

未参加
状态
已结束
规则
IOI
题目
19
开始于
2023-1-9 12:00
结束于
2023-1-17 20:00
持续时间
200 小时
主持人
参赛人数
12