Report(報告) - joi2011-day3

出典: 第10回日本情報オリンピック 日本代表選手選考会

時間制限: 0.5秒

メモリ制限: 64MB

情報オリンピック日本委員会は報告・連絡・相談が非常に徹底された組織である．委員会には N 人が所属し，すべての人に対しその報告を受ける人 (「報告先」と呼ぶ) が 1 人ずつ定まっている．

今，情報オリンピック日本委員会の中で，あるプロジェクトを立ち上げることとなった．このプロジェクトは，仕事 1, 仕事 2, …, 仕事 N という N 個の仕事に分けられており，N 人には一つずつ異なる担当が割り当てられている．N 個の仕事は仕事 1 から仕事 N まで番号順に処理される．ある仕事の担当者がその仕事を終えたとき，その人は自分の「報告先」に対して「作業報告」を行う．「作業報告」を受けた人は，それと同一の「作業報告」を自分の「報告先」に対して行う．ただし，同じ「作業報告」を既に自分の「報告先」にしたことがある場合は，同じ仕事に対する「作業報告」を再びすることはない．これが繰り返されることで， 委員会中の何人かが「作業報告」を受けることとなる．次の仕事は，前の仕事の「作業報告」が全て行われてから処理される．

課題

入力として各仕事の担当者の「報告先」が与えられたとき，それぞれの人が自分の仕事に取りかかる段階において，受けた「作業報告」の種類の数を出力するプログラムを作成せよ．

制限

2 \leq N \leq 100\,000 委員会に所属する人数

入力

標準入力から以下の入力を読み込め．

出力

出力は N 行からなる. i 行目 (1 \leq i \leq N) に，仕事 i の担当者が仕事に取りかかる段階において，受けた「作業報告」の種類の数を表す 1 つの整数を出力せよ.

採点基準

入出力の例

入力例 出力例
6
3
4
2
6
3
2		 0
1
1
3
0
5

この入力例では，以下のようになる．