- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
- آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران
یاسین تصمیم گرفته شجرهنامهی خانواده خود را بسازد.
او تصویر \(n + 1\) نفر را در اختیار دارد. همچنین سن هر کدام از افراد را میداند. اما از بین این افراد فقط بزرگ خاندان را میشناسد.
یاسین نزد بزرگ خاندان میرود تا از او برای ساخت شجرهنامه کمک بگیرد. اما بزرگ خاندان به او میگوید این مسخرهبازیا چیه بچه و برای او یک سوال مطرح میکند تا توانایی درخت ساختنش را به چالش بکشد.
بزرگ خاندان به یاسین میگوید که برایش یک درخت ریشهدار بسازد. هر راس این درخت یک اندیس دارد و روی راس با اندیس \(i\)، عدد \(a_i\) نوشته شده است. در ابتدا درخت یک راس با اندیس \(0\) دارد که روی آن عدد \(+\infty\) نوشته شده است.
بزرگ خاندان در \(n\) مرحله، هر مرحله یک راس به درخت اضافه میکند.
او در مرحلهی \(i\)-ام عدد \(p_i\) را به یاسین میگوید و سپس از او میخواهد راس \(i\) را به یکی از دو نحو زیر به درخت اضافه کند:
- راس \(i\) را فرزند راس \(p_i\) قرار میدهد؛ یعنی یک یال بین راس \(i\) و \(p_i\) میکشد. (\(0 \leq p_i < i\))
- بزرگترین خاندان ابتدا از یاسین میخواهد که پایین ترین جد راس \(p_i\) را پیدا کند که عددش از \(a_i\) کمتر نباشد. (\(0 \leq p_i < i\)) در صورتی که \( a_{p_i} \geq a_i\) ، راس \(i\) را فرزند راس \(p_i\) قرار میدهد؛ یعنی یک یال بین راس \(i\) و \(p_i\) میکشد. در غیر این صورت یاسین باید رئوس \(v\) و \(u\) را طوری پیدا کند که :
- هر دو جد راس \(p_i\) باشند. (راس \(p_i\) هم یکی از اجداد خودش است.)
- راس \(v\) پدر راس \(u\) باشد.
- نامساوی \(a_u < a_i \leq a_v\) و به ازای هر راس مانند \(z\) که \(v\) جد \(z\) و \(z\) جد \(p_i\) باشد داریم \(a_z < a_i\)
- حال راس \(i\) را وسط یال \(v\) و \(u\) اضافه میکنیم. یعنی راس \(v\) پدر راس \(i\) و راس \(i\) پدر راس \(u\) میشود.
در انتها بزرگ خاندان از او میخواهد به ازای هر راس از \(1\) تا \(n\) پدرش در درخت نهایی را به او بگوید. یاسین که از برآورده کردن خواستههای پیرمردها و درختهایشان خسته شده بود از شما میخواهد کمکش کنید تا خود را به بزرگ خاندان ثابت کند.
ورودی
در خط اول ورودی \(n\) می آید. \[1 \leq n \leq 10^6\]
سپس در خط \(i\)ام از \(n\) خط بعدی، سه عدد \(t_i\)، \(p_i\) و \(a_i\) به ترتیب آمده اند. \[t_i \in \{1, 2\} ,\quad 0 \leq p_i < i, \quad 1 \leq a_i \leq n\]
اگر \(t_i\) برابر با \(1\) بود این عملیات از نوع اول و اگر برابر با \(2\) بود از نوع دوم است.
خروجی
در تنها خط خروجی باید \(n\) عدد چاپ کنید که عدد \(i\) ام باید پدر راس \(i\) در درخت نهایی باشد.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۷ | \(n \leq 5000\) |
| ۲ | ۱۲ | \(a_i \leq 2\) |
| ۳ | ۸۱ | بدون محدودیت اضافی |
مثالها
ورودی نمونه ۱
6
2 0 1
1 1 3
2 2 6
2 1 1
2 4 4
2 3 3
خروجی نمونه ۱
5 1 0 1 3 3