مترسک به گاتهام آمده و مردم شهر را مسموم کرده است. بتمن با کمک دستیارانش توانسته پادزهری بسازد که مردم را شفا بدهد و حالا می‌خواهد آن را بین مردم پخش کند. نقشه شهر گاتهام به صورت یک درخت $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$
• زیرمسئله ۶ (۱۱ نمره): بدون محدودیت اضافی

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