- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!
رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!
تبریک! شما کیک پخش‌کن جلسه‌ی کنکور شده‌اید! باید کاری برای حلی سه‌ای هایِ دوست داشتنی انجام دهید! حلی سه‌ای ها از روش‌های پیشرفته‌ی تقلب استفاده می‌کنند! یکی از این روش‌ها درخت تقلب است! به این صورت که هر نفر به یک راس متناظر میشود!
از طرف حلی سه‌ای ها(!) از شما خواسته شده که برای تقلب آسان تر کار‌های زیر را بی‌چون و چرا انجام دهید!
در ابتدا یک راس به منزله‌ی مقر فرماندهی(با شماره ۱) داریم که از دیشب سر صندلی خود حاضر بوده است. هر بار یکی از این دو کار را انجام می‌دهیم:
-
1 p: طبق برنامه یک حلی سه‌ای وارد میشود! اگر قبل از ورود این فرد $k$ فرد سر جلسه حضور داشتند ما شماره‌‌ی $k+1$ را به آن فرد اختصاص می‌دهیم و آن را به راس شماره $p$ وصل می‌کنیم. -
d v 2: دورترین راس از مقر فرماندهی را که با $v$ حداکثر $d$ یال فاصله دارد را پیدا می‌کنیم و آن را گزارش می‌دهیم!
همانطور که معلوم است. گراف همیشه درخت باقی می‌ماند.
ورودی
در خط اول ورودی $q$ تعداد کوئری‌ها می‌آید. سپس $q$ خط هر کدام همان طور که شرح داده شد آمده‌اند. $$1 \leq q \leq 200\ 000 $$ $$0 \leq d \leq 1\ 000\ 000\ 000$$ در کوئری‌ها تضمین میشود راس $p$ و $v$ در گراف وجود دارند.
خروجی
به ازای هر کوئری نوع دو، جواب آن را چاپ کنید.
اگر چند جواب درست وجود داشت یکی از آن‌ها را به دلخواه چاپ کنید.
مثال
ورودی نمونه ۱
5
1 1
1 1
2 2 10
1 3
2 2 10
خروجی نمونه ۱
2
4
ورودی نمونه ۲
9
1 1
1 1
1 2
2 3 3
1 4
2 3 4
1 4
1 6
2 4 2
خروجی نمونه ۲
4
5
7
ارسال پاسخ برای این سؤال