Ủy ban Olympic Tin học Nhật Bản là một tổ chức rất coi trọng việc báo cáo, liên lạc và trao đổi. Ủy ban có \(N\) người; mỗi người có đúng một người được chỉ định làm người nhận báo cáo của mình.

Ủy ban sắp triển khai một dự án gồm \(N\) công việc, được đánh số từ \(1\) đến \(N\). Mỗi người được giao phụ trách một công việc khác nhau. Các công việc được thực hiện lần lượt theo thứ tự từ công việc \(1\) đến công việc \(N\).

Khi hoàn thành công việc, người phụ trách gửi một báo cáo công việc cho người nhận báo cáo của mình. Người nhận được báo cáo tiếp tục chuyển chính báo cáo đó đến người nhận báo cáo của họ. Tuy nhiên, nếu một người đã từng chuyển báo cáo về công việc đó thì người ấy không chuyển lại báo cáo đó nữa. Quá trình này được lặp lại, nhờ đó một số người trong ủy ban nhận được báo cáo. Chỉ sau khi tất cả việc chuyển báo cáo của công việc trước kết thúc, công việc tiếp theo mới được thực hiện.

Yêu cầu

Cho biết người nhận báo cáo của người phụ trách từng công việc. Với mỗi người, hãy tính số loại báo cáo công việc khác nhau mà người đó đã nhận được tại thời điểm bắt đầu thực hiện công việc của mình.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số người trong ủy ban.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i+1\) \((1\le i\le N)\) chứa số nguyên \(A_i\). Người nhận báo cáo của người phụ trách công việc \(i\) là người phụ trách công việc \(A_i\).

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) \((1\le i\le N)\) chứa một số nguyên là số loại báo cáo công việc khác nhau mà người phụ trách công việc \(i\) đã nhận được khi bắt đầu công việc của mình.

Ràng buộc

• \(2\le N\le100\,000\).
• \(1\le A_i\le N\) và \(A_i\ne i\) với mọi \(1\le i\le N\).

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(0{,}5\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(N\le1\,000\).

Ví dụ

6
3
4
2
6
3
2

0
1
1
3
0
5