+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به شما یک گراف همبند $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 ```