حمل و نقل عمومی (Public Transport)

رابین‌هود که مدتی از ناتینگهام خارج شده بود،‌ هنگام برگشتش با وسیله‌ی حمل و نقل عجیبی که تازه تاسیس شده بود مواجه شد، تلپورتر! این وسیله هر لحظه منتظر می‌ماند تا تعداد کسانی که می‌خواهند از آن استفاده کنند به حد نصاب برسد، سپس آن‌ها را در یک چشم به هم زدن به ایستگاه بعد منتقل می‌کند! اگر کسانی که تازه به یک ایستگاه رسیده‌اند قصد رفتن به ایستگاه بعدی را داشته باشند و تعداد متقاضیان دستگاه بعدی پس از رسیدن مسافران ایستگاه قبل به حد نصاب برسد، در همان لحظه آن دستگاه هم مسافران را منتقل می‌کند. اما اگر مسافران به مقصد خود برسند درجا پیاده می‌شوند و کسی از ایستگاه مقصد خود رد نمی‌شود. تنها ضعف این نوآوری جدید ناتینگهام این است که فقط افراد را از ارتفاع پایین‌تر به بالاتر منتقل می‌کند!

به عبارت دیگر، یک درخت ریشه‌دار $n$ راسی داریم که راس شماره $1$ ریشه آن است. در هر راس به غیر از ریشه، یک ایستگاه وجود دارد که زمانی که تعداد افرادی که می‌خواهند از این راس بالا بروند به حد نصاب برسد، تمام مسافران را در لحظه به راس پدر انتقال می‌دهد. دقت کنید ممکن است در یک ثانیه یک نفر چندین ایستگاه بالا برود.

در ابتدای روز تمام ایستگاه‌ها خالی هستند، در ثانیه‌ی $i$ام یک مسافر جدید وارد شده که می‌خواهد از یکی از ایستگاه‌ها به یکی از اجدادش برود. حال از شما می‌خواهیم برای هر مسافر خروجی بدهید که در کدام ثانیه به مقصدش می‌رسد یا مشخص کنید که هیچوقت به مقصد نمی‌رسد.

در خط اول، تعداد رئوس درخت یا همان $n$ می‌آید.

در خطوط دوم تا $n$ام، در هر خط دو عدد $p_i$ و $k_i$ می‌آید که به ترتیب راس پدر و حداقل تعداد مسافر وسیله‌ی راس $i$ را نشان می‌دهند.

در خط $n + 1$، تعداد مسافران یا همان $m$ ورودی داده می‌شود.

در $m$ خط بعدی، در هر خط دو ورودی $a_i$ و $b_i$ داده می‌شود که مبدا و مقصد مسافر $i$ام را نشان می‌دهد.

در تنها خط خروجی به ترتیب زمان خروج هر مسافر را چاپ کنید. در صورتی که مسافر هیچوقت به مقصد نمی‌رسید، عدد $-1$ را چاپ کنید.

• زیرمسئله اول (۷ نمره): $1 \leq n, m \leq 3000$.
• زیرمسئله دوم (۳۰ نمره): $p_i = i - 1$.
• زیرمسئله سوم (۱۸ نمره): $k_i = 2$.
• زیرمسئله چهارم (۱۷ نمره): $b_i = 1$.
• زیرمسئله پنجم (۲۸ نمره): بدون محدودیت اضافی.

• $2 \leq n, m \leq 2 \times 10^5$
• $2 \leq k_i \leq 2 \times 10^5$
• $1 \leq p_i < i$
• تضمین می‌شود $b_i$ یکی از اجداد $a_i$ است. همچنین مبدا و مقصد هیچ مسافری یکسان نیست.

3
1 2
2 1
3
2 1
3 2
2 1

3 2 3

4
1 2
2 2
2 1
6
3 1
3 2
3 1
4 1
4 1
3 1

4 2 6 4 6 6

در نمونه اول ابتدا مسافر اول در ایستگاه ۲ منتظر می‌ماند تا یک نفر دیگر هم بخواهد از آن استفاده کند، سپس نفر دوم می‌خواهد از ایستگاه راس ۳ استفاده کند که چون حد نصابش یک است، درجا به راس دو می‌رسد، ولی دستگاه راس ۲ فعال نمی‌شود، چون نفر دوم به محض رسیدن به راس ۲ از ایستگاه خارج می‌شود، سپس در ثانیه‌ی سوم نفر دوم به ایستگاه ۲ می‌آید و افراد یک و سه در ثانیه‌ی سوم به مقصد خود می‌رسند.