فهرست مندرجات

زیردرخت مینیمال (Minimal Subtree)

یک درخت $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$ ام را خروجی دهید.

زیرمسئله‌ها

محدودیت‌ها

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5 3
1 2
1 3
2 4
2 5
3 5
1 4
1 3
5
4
3
7 10
6 5
3 6
7 4
4 5
1 6
4 2
1 5
3 6
4 5
1 6
2 3
4 4
2 6
2 2
1 6
2 5
6
4
2
6
5
1
5
1
6
5