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

---

به شما یک گراف همبند $n$ راسی با $n - 1$ یال داده می‌شود. شما باید $q$ عملیات را روی این گراف انجام دهید.

هرکدام از این عملیات‌ها به یکی از دو صورت می‌باشد:

• 1 v
• 2 u v

عملیات اول به این صورت است که باید راس $v$ را از گراف باقیمانده حذف کنید. عملیات دوم نیز به این صورت است که باید یال بین دو راس $u$ و $v$ را از گراف باقیمانده حذف کنید. همچنین پس از اعمال هر عملیات باید مجموع فواصل هر دو راسی که درون یک مولفه هستند را خروجی دهید.

ورودی

در خط اول ورودی به شما دو عدد $n$ و $q$ داده می‌شود که به ترتیب بیانگر تعداد راس‌های گراف و تعداد عملیات‌ها می‌باشند.

در $n - 1$ خط بعدی، در هر خط دو عدد $u$ و $v$ داده می‌شود که بیانگر این است که بین راس‌های $u$ و $v$ یک یال وجود دارد.

در $q$ خط بعدی، در هر خط به شما یک عملیات داده می‌شود که یا از نوع اول می‌باشد یا از نوع دوم می‌باشد.

تضمین می‌شود گراف ورودی همبند است و همچنین در هنگام عملیات های نوع اول و دوم، به ترتیب راس و یال مورد نظر در گراف موجود است. $$ 1 \le n \le 500\ 000$$ $$ 1 \le q \le 2n - 1 $$ $$ 1 \le u, v \le n $$ $$ u \neq v $$

خروجی

خروجی شامل $q$ خط است که خط $i$ام برابر با مجموع فواصل هر دوراسی که درون یک مولفه هستند، پس از اعمال عملیات $i$ام می‌باشد.

مثال

ورودی نمونه ۱

4 1
1 2
2 3
3 4
2 1 2

خروجی نمونه ۱

4

ورودی نمونه ۲

5 2
1 2
2 3
3 4
3 5
2 2 3
1 3

خروجی نمونه ۲

5
1