Trick or Treat on the Farm

Time limit1sMemory limit128 MB

Summary

Each stall has one outgoing next pointer. For every starting stall, count how many distinct stalls the walk visits before it first revisits a stall.

Level: Medium6 of 10
Topics: Graph, DFS, Implementation, Array
Solved: No attempts yet

Problem

Every year in Wisconsin the cows celebrate the American autumn holiday of Halloween by dressing up in costumes and collecting the candy that Farmer John leaves in the $N$ ( $1 \le N \le 100{,}000$ ) stalls, conveniently numbered $1 \dots N$ .

Because the barn is not very large, FJ makes the fun last longer by specifying a traversal route the cows must follow. To do this he posts on each stall $i$ a "next stall number" $next_i$ ( $1 \le next_i \le N$ ) that tells the cows which stall to visit next; the cows may therefore travel back and forth through the barn many times while collecting candy.

FJ requires that cow $i$ start collecting candy at stall $i$ . A cow stops collecting the moment she arrives at any stall she has already visited.

Compute the number of distinct stalls each cow visits before she is forced to stop.

Input

Line 1: a single integer $N$ .
Lines 2 to $N+1$ : line $i+1$ contains a single integer $next_i$ .

Output

Lines 1 to $N$ : line $i$ contains a single integer, the total number of distinct stalls visited by cow $i$ before she returns to a stall she has already visited.

Examples3

Example 1
Input
```
4
1
3
2
3
```
Expected output
```
1
2
2
3
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
5
2
3
4
5
5
```
Expected output
```
5
4
3
2
1
```