• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران

---

‌ا Scarecrow به گاتهام آمده و مردم شهر را مسموم کرده است. Batman با کمک دستیارانش توانسته پادزهری بسازد که مردم را شفا بدهد و حالا می‌خواهد آن را بین مردم پخش کند. نقشه شهر گاتهام به صورت یک درخت $n$ راسی می‌باشد که هر راس از آن یک منطقه را نشان می‌دهد. بتمن یک منطقه مانند $v$ را انتخاب می‌کند و پادزهر را از آن منطقه منتشر می‌کند. بتمن با افسر گوردن هماهنگ کرده است تا دقیقا یکی از جاده‌ها (یال) را غیر قابل عبور کند تا اهالی منطقه $v$ نتوانند از فاصله $k$ این منطقه دورتر بروند زیرا اگر بتوانند خود را به منطقه‌ای برسانند که فاصله آن با $v$ حداقل $k$ جاده باشد، پادزهر روی آن‌ها اثر نمی‌کند.

به همین خاطر افسر گوردن از بتمن می‌خواهد تا تعداد جاده‌هایی که با بسته شدن آن‌ها پادزهر اثر نمی‌کند را به او بگوید. بتمن که هنوز راس اولیه و مقدار $k$ را انتخاب نکرده است، از شما کمک می‌خواهد تا این تعداد را به ازای $Q$ سناریو مختلف جواب دهید.

ورودی

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

در خط بعدی دنباله $p_2, p_3, \cdots, p_{n}\ $ می‌آیند. به ازای هر $2 \leq i \leq n$ جاده‌ای میان دو منطقه $i$ و $p_i$ وجود دارد.

در هر یک از $q$ خط بعدی، دو عدد طبیعی $v_i$ و $k_i$ می‌آیند.

خروجی

در $q$ خط جواب مربوط به هر سناریو را چاپ کنید.

محدودیت‌ها

$$1 \leq n, q \leq 300 , 000$$ $$1 \leq p_i \leq i - 1$$ $$1 \leq v_i, k_i \leq n$$

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۸	$p_i = i-1$ به ازای تمامی $2 \leq i \leq n$ برقرار است.
۲	۱۳	$n \leq 300$ و $q \leq 1000$
۳	۲۲	$n, q\leq 1000$
۴	۱۸	$n, q \leq 100 , 000$ و فاصله منطقه $1$ با دورترین منطقه از آن حداکثر $40$ جاده می‌باشد.
۵	۲۸	$n, q \leq 100 , 000$
۶	۱۱	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

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

خروجی نمونه ۱

2
4
3
2
0

ورودی نمونه ۲

10 1
1 2 3 4 5 4 7 6 9
8 5

خروجی نمونه ۲

7

گراف ورودی دوم به شکل زیر است.

شکل ۱: شکل گراف نمونه ورودی ۲

اگر افسر گوردن هر جاده‌ای به جز جاده‌های بین $\langle 4, 7 \rangle$ یا $\langle 7, 8 \rangle$ را ببندد، مردم می‌توانند از منطقه $8$ به حداقل یکی از مناطق $1$ یا $9$ بروند و پادزهر روی آن‌ها اثر نگذارد.