[USACO08DEC] Trick or Treat on the Farm G

#### 题目描述 每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在 $N(1\le N\le 100,000)$ 个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。 由于牛棚不太大，FJ 通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ 在第 $i$ 号隔间上张贴了一个 “下一个隔间：$next_i(1\le next_i\le N)$” 的标语，告诉奶牛要去的下一个隔间。这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。 FJ 命令奶牛 $i$ 应该从 $i$ 号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。 在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。 #### 输入格式 第一行一个整数 $n$，表示牛棚隔间的数量。 第 $2$ 至 $n+1$ 行，每行包含一个整数 $next_i$，表示 $i$ 号隔间的下一个隔间。 #### 输出格式 输出共 $n$ 行，第 $i$ 行包含一个整数，表示第 $i$ 只奶牛要前往的隔间数。 #### 样例解释 有 $4$ 个隔间。 - 隔间 $1$ 要求牛到隔间 $1$， - 隔间 $2$ 要求牛到隔间 $3$， - 隔间 $3$ 要求牛到隔间 $2$， - 隔间 $4$ 要求牛到隔间 $3$。 牛 $1$：从 $1\rightarrow 1$，总共访问 $1$ 个隔间； 牛 $2$：$2\rightarrow 3\rightarrow 2$，总共访问 $2$ 个隔间； 牛 $3$：$3\rightarrow 2\rightarrow 3$，总共访问 $2$ 个隔间； 牛 $4$：$4\rightarrow 3\rightarrow 2\rightarrow 3$，总共访问 $3$ 个隔间。 翻译提供者：[busy_programmer](https://www.luogu.com.cn/user/649315)。

Every year in Wisconsin the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N (1 <= N <= 100,000) stalls conveniently numbered 1..N. Because the barn is not so large, FJ makes sure the cows extend their fun by specifying a traversal route the cows must follow. To implement this scheme for traveling back and forth through the barn, FJ has posted a 'next stall number' next\_i (1 <= next\_i <= N) on stall i that tells the cows which stall to visit next; the cows thus might travel the length of the barn many times in order to collect their candy. FJ mandates that cow i should start collecting candy at stall i. A cow stops her candy collection if she arrives back at any stall she has already visited. Calculate the number of unique stalls each cow visits before being forced to stop her candy collection. POINTS: 100

\* Line 1: A single integer: N \* Lines 2..N+1: Line i+1 contains a single integer: next\_i

\* Lines 1..N: Line i contains a single integer that is the total number of unique stalls visited by cow i before she returns to a stall she has previously visited.

4 
1 
3 
2 
3 

1 
2 
2 
3 

Four stalls. \* Stall 1 directs the cow back to stall 1. \* Stall 2 directs the cow to stall 3 \* Stall 3 directs the cow to stall 2 \* Stall 4 directs the cow to stall 3 Cow 1: Start at 1, next is 1. Total stalls visited: 1. Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.