- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: JOI 2013
اصغر پرنده همانطور که از اسمش پیداست در یک درخت زندگی میکند. این درخت \(n\) راس دارد که با \(n-1\) یال به هم وصل شده اند. در هر راس این درخت یک گنده لات نشسته است.
هر گنده لات یکی از اسرار محرمانه دولت را میداند (اسراری که لاتها میدانند متفاوت اند). سازمان امنیت کشور که نمیخواهد اطلاعات پخش شود، تمام یالهای درخت را بسته است.
اکبر چرنده، برادر اصغر، که از نیروهای شورشی است تصمیم دارد یالها را باز کند تا اطلاعات پخش شوند. هر روز یا اکبر یک یال بسته را باز میکند و یا سازمان امنیت یک یال باز را میبندد.
با باز شدن هر یال دو لاتی که در دو سر یال نشسته اند، اسراری که میدانند را برای هم فاش میکنند و سپس هرکدام اسرار جدیدی که فهمیده اند را برای تمام لاتهایی که میتوانند با طی کردن تعدادی یال باز به آنها برسند فاش میکنند.
این عملیات تا \(m\) روز ادامه پیدا کرد تا اینکه اکبر را توی گونی کرده و بردند. اصغر به ازای هریک از این \(m\) روز شماره یالی که وضعیتش تغییر کرده را به شما داده و در نهایت میخواهد به ازای \(q\) تا از لاتها، تعداد اسرار محرمانه ای که میدانند را به او بگویید.
ورودی
در خط اول ورودی سه عدد \(n\) و \(m\) و \(q\) آمده اند که تعداد رئوس درخت، تعداد روزهای عملیات، و تعداد کسانی که اصغر از شما تعداد اسراری که میدانند را میخواهد را نشان میدهند.
در خط \(i\)ام از \(n-1\) خط بعدی، دو عدد \(u_{i}\) و \(v_{i}\) آمده اند که شماره رئوس دو سر یال \(i\)ام را نشان میدهند. (شماره دو سر یال از ۱ تا \(n\) است)
در \(m\) خط بعدی شماره یالهایی که عملیات روی آنها انجام شده آمده است. (شمارهها از ۱ تا \(n-1\) است)
و \(q\) خط بعدی هم نشان دهنده شماره رئوسی است که باید تعداد اسرار لاتهایشان را خروجی دهید. این \(q\) عدد بین ۱ تا \(n\)، و متفاوت اند.
\[1 \le q \le n \le 100\ 000\] \[1 \le m \le 200\ 000\]
خروجی
در خروجی باید جواب \(q\) درخواست را در خطوط جداگانه چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۳۰ | \(q=1\) |
| ۲ | ۳۰ | \(u_{i}=i\) و \(v_{i}=i+1\) |
| ۳ | ۴۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
خروجی نمونه
3
5
4
اگر فرض کنیم در ابتدای کار لات شماره \(i\) اطلاعات شماره \(i\) را دارد، اطلاعاتی که افراد در انتهای این 6 روز میدانند به این شکل خواهد بود:
یال شماره 1 باز میشود. \[(1,2),(1,2),(3),(4),(5)\] یال شماره 2 باز میشود. \[(1,2,3),(1,2,3),(1,2,3),(4),(5)\] یال شماره 1 بسته میشود. \[(1,2,3),(1,2,3),(1,2,3),(4),(5)\] یال شماره 4 باز میشود. \[(1,2,3),(1,2,3,5),(1,2,3),(4),(1,2,3,5)\] یال شماره 4 بسته میشود. \[(1,2,3),(1,2,3,5),(1,2,3),(4),(1,2,3,5)\] یال شماره 3 باز میشود. \[(1,2,3),(1,2,3,4,5),(1,2,3),(1,2,3,4,5),(1,2,3,5)\]