درخت تقلب

در ابتدا یک راس به منزله‌ مقر فرماندهی داریم که از دیشب سر صندلی خود حاضر بوده است.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

رتبه‌ ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!
رتبه‌ یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

تبریک! شما کیک پخش‌ کن جلسه‌ کنکور شده‌ اید! باید کاری برای حلی سه‌ ای هایِ دوست داشتنی انجام دهید! حلی سه‌ ای ها از روش‌ های پیشرفته‌ تقلب استفاده می‌ کنند! یکی از این روش‌ ها درخت تقلب است! به این صورت که هر نفر به یک راس متناظر می‌ شود!
از طرف حلی سه‌ ای‌ ها(!) از شما خواسته شده که برای تقلب آسان تر کار‌های زیر را بی‌ چون و چرا انجام دهید!

در ابتدا یک راس به منزله‌ مقر فرماندهی (با شماره ۱) داریم که از دیشب سر صندلی خود حاضر بوده است. هر بار یکی از این دو کار را انجام می‌دهیم:
1 p : طبق برنامه یک حلی سه‌ ای وارد می‌شود! اگر قبل از ورود این فرد kkk فرد سر جلسه حضور داشتند ما شماره‌‌ k+1k+1k+1 را به آن فرد اختصاص می‌ دهیم و آن را به راس شماره ppp وصل می‌کنیم.
d v 2 : دورترین راس از مقر فرماندهی را که با vvv حداکثر ddd یال فاصله دارد را پیدا می‌کنیم و آن را گزارش می‌ دهیم!
همان طور که معلوم است. گراف همیشه درخت باقی می‌ماند.

ورودی
در خط اول ورودی qqq تعداد کوئری‌ ها می‌ آید. سپس qqq خط هر کدام همان طور که شرح داده شد آمده‌ اند. 1≤q≤200 0001 leq q leq 200 000 1≤q≤200 000 0≤d≤1 000 000 0000 leq d leq 1 000 000 0000≤d≤1 000 000 000 در کوئری‌ ها تضمین می شود راس ppp و vvv در گراف وجود دارند.

خروجی
به ازای هر کوئری نوع دو، جواب آن را چاپ کنید.
اگر چند جواب درست وجود داشت یکی از آن‌ها را به دلخواه چاپ کنید.

مثال
ورودی نمونه ۱
5
1 1
1 1
10 2 2
3 1
10 2 2

خروجی نمونه ۱
2
4

ورودی نمونه ۲
9
1 1
1 1
2 1
3 3 2
4 1
4 3 2
4 1
6 1
2 4 2

خروجی نمونه ۲
4
5
7


مرکز یادگیری سایت تبیان