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

سرکه نماد پذیرش ناملایمات زندگی است.

یک درخت $n$ راسی داریم که در ابتدا تمام رئوسش به رنگ سرکه‌ای هستند. $q$ پرسمان به شما داده می‌شود. پرسمان‌ها از دو نوع هستند.

• نوع اول: رنگ راس $v$ را عوض کنید. اگر به رنگ سرکه‌ای بود، به رنگ سبز کله غازی در بیاورید و اگر سبز کله غازی بود به رنگ سرکه‌ای در بیاورید.
• نوع دوم: مجموع فاصله‌ی بین تمام جفت راس‌های به رنگ سرکه‌ای را خروجی دهید.

فاصله دو راس برابر تعداد یال‌هایی است که در کوتاه‌ترین مسیر بین دو راس وجود دارد.

ورودی

در سطر اول دو عدد صحیح $n$ و $q$ به‌ترتیب می‌آیند. که بیانگر تعداد راس‌ها و تعداد پرسمان‌هاست.
در $n-1$ سطر بعدی در هر سطر یال‌های درخت ورودی داده می‌شود. در هر یک از $q$ سطر بعدی پرسمان‌ها می‌آیند که هر کدام به یکی از دو شکل زیر هستند.

• 1 v: رنگ راس $v$ عوض می‌شود.
• 2: مجموع فواصل را پیدا کنید.

$$1 \le n, q \le 10^5$$ $$1 \le v \le n$$

خروجی

به ازای هر پرسمان از نوع دوم مجموع فواصل را در یک سطر جدید چاپ کنید.

مثال

ورودی نمونه ۱

3 3
1 2
2 3
2
1 2
2

خروجی نمونه ۱

4
2

در اولین پرسمان نوع دوم تمام رئوس به رنگ سرکه‌ای هستند و فاصله‌های تمام جفت رئوس سرکه‌ای به نحو زیر است:

فاصله‌ی راس ۱ با راس ۲ برابر ۱ است، فاصله راس ۱ با راس ۳ برابر ۲ است، فاصله راس ۲ با راس ۳ برابر ۱ است.

پس مجموعه فواصل رئوس به رنگ سرکه‌ای برابر ۴ است.

در دومین پرسمان نوع دوم تنها رئوس ۱ و ۳ به رنگ سرکه‌ای هستند و راس ۲ به رنگ سبز کله‌ غازی است.

فاصله‌ی راس ۱ با راس ۳ برابر ۲ است، پس مجموعه فواصل رئوس به رنگ سرکه‌ای برابر ۲ است.

ورودی نمونه ۲

4 9
1 2
1 3
3 4
2
1 1
2
1 3
2
1 2
2
1 1
2

خروجی نمونه ۲

10
6
3
0
2