P2921 [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)。

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.