یک درخت $n$ راسی داریم که راس‌های آن با $1$ تا $n$ شماره‌گذاری شده‌اند.

به شما $q$ کوئری داده می شود. در هر کوئری دو عدد $l$ و $r$ به شما ورودی داده می‌شود و شما باید اندازه کوچکترین زیرمجموعه همبند از رئوس درخت که شامل تمام رئوس $l$ تا $r$ هستند را خروجی دهید.

در خط اول ورودی $n$ و سپس $q$ می‌آید.

در هر یک از $n-1$ خط بعدی دو عدد $v_i$ و $u_i$ می‌آید که نمایانگر یال‌های درخت است.

در $i$ امین خط از $q$ خط بعدی دو عدد $l_i$ و $r_i$ می‌آید که نمایانگر کوئری $i$ ام است.

در $i$ امین خط از خروجی پاسخ کوئری $i$ ام را خروجی دهید.

• زیرمسئله اول (۷ نمره): $n, q \leq 2\,000$
• زیرمسئله دوم (۸ نمره): درخت ورودی مسیر است.
• زیرمسئله سوم (۱۲ نمره): $n, q \leq 100\,000, r_i - l_i \leq 100$
• زیرمسئله چهارم (۱۸ نمره): $n, q \leq 50\,000$
• زیرمسئله پنجم (۵۵ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۶ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $n \leq 250\,000$
• $q \leq 1\,000\,000$
• $1 \leq v_i, u_i \leq n$
• $1 \leq l_i \leq r_i \leq n$

• سوال قبل
• سوال بعد