Problem
یک بار کنستانتین، پس از شرکت در المپیاد بعدی، در حال حاضر سیزدهمین المپیاد بین المللی، با قطار به خانه برمی گشت. او مثل همیشه نشسته بود و به معنای زندگی فکر می کرد و همزمان مشکلات برنامه نویسی را حل می کرد. پس از مدتی، کنستانتین چرت زد، اما مشکل اینجاست که برای بیدار شدن، باید مشکلی را که در سرش ظاهر شده و او را آزار می دهد، حل کند!
کنستانتین این بار رویای درختی را دید که در ابتدا فقط از یک راس با عدد 1 تشکیل شده بود. در مسئله ای که او تعیین کرد، به تدریج رئوس جدیدی به درخت اضافه شد. در ثانیه i یک راس با عدد i+1 به درخت اضافه شد که به صورت son از راس p
i و در لبه بین رئوس i+1 معلق بود. و p
i حرف c
i نوشته شد.
هر مسیر از ریشه درخت تا راس v مربوط به رشته خاصی است که با نوشتن نمادهای نوشته شده در لبه های مسیر فعلی به ترتیب از ریشه تا راس v به دست می آید. کنستانتین در نگاه اول با کار دشواری روبرو شد - پس از هر بار افزودن یک راس جدید، تعداد رشته های منحصر به فردی را که از ریشه درخت شروع می شود (رأس شماره 1) و به یک راس دیگر ختم می شود، بشمارید.
کنستانتین در رویای خود اصلاً نابغه نیست، بنابراین او خودش نمی تواند این مشکل را حل کند. به کنستانتین کمک کنید مشکل را حل کند و بیدار شود.
ورودی:
خط اول شامل عدد n است - تعداد درخواست‌ها برای افزودن یک گره جدید به درخت (1 <= n <= 300000).
n خط بعدی درخواست های اضافه کردن رئوس را توضیح می دهد. i-امین پرس و جو با پارامترهای p
i (1 <= p
i <= i) و c
i توصیف می‌شود. به این معنی که راس اضافه شده با عدد i+1 از راس با عدد p
i در کودکی معلق است و نماد c
i در لبه حاصل نوشته می شود - یک حرف کوچک از الفبای لاتین.
خروجی:
چاپ n خط. پس از افزودن راس i+1، پاسخ مسئله کنستانتین را در خط i ام چاپ کنید.
مثال:
<بدن>
| ورودی |
خروجی |
2
1 ب
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |