PEG Judge - WC15 #4 - World Tour

Woburn Challenge 2015-16 Round 4 - Senior Division

Problem 2: World Tour

James Bond is in trouble – the fearsome Jaws is after him! Jaws will stop at nothing to find Bond and take him out (and not out to eat, though biting will be involved), and he's gotten incredibly skilled at picking up Bond's trail as he travels around the world on his assignments.

Unfortunately for Jaws, this ability to follow Bond's trail will be his undoing. Bond intends to take Jaws on a little world tour, tricking him into flying to all sorts of cities by leaving behind fake clues about where he himself is headed.

There are N (1 ≤ N ≤ 500,000) cities of interest, and in the i-th of these cities, Bond will leave a clue suggesting that he travelled from that city to a different city C_i (1 ≤ C_i ≤ N, C_i ≠ i). This means that, if Jaws ever finds himself in city i, he's sure to fly to city C_i from there!

Depending on which city Jaws starts in, the sequence of flights he'll be obligated to take while following Bond's supposed trail will differ. In fact, each such sequence of flights will be infinitely long, as poor Jaws will always blindly go on chasing his adversary's scent, even if he passes through some of the cities multiple times along the way! It's a good thing he'll be able to file an expense report to get reimbursed for all of these flights afterwards (they're for business purposes, after all). That being said, over the course of his infinitely-long trip, he certainly won't visit an infinite number of different cities. For each of the N potential starting cities, can you count the number of different cities (including that one) which Jaws will end up visiting if he starts there and continues taking his required flights forever?

Subtasks

In test cases worth 7/23 of the points, N ≤ 2000.

Input Format

The first line of input consists of a single integer N.
The next N lines each consist of a single integer C_i, for i = 1..N.

Output Format

Output N lines, one integer per line. The i-th line (for i = 1..N) should consist of the number of different cities that Jaws will end up visiting if he starts in city i.