Problem
یکی از سازمان‌های بسیار محرمانه که ما اجازه نداریم نامش را فاش کنیم، شبکه‌ای از پناهگاه‌های زیرزمینی
N است که توسط تونل‌هایی با طول مساوی به هم متصل شده‌اند و از طریق آن می‌توان از هر پناهگاهی به پناهگاه دیگر رفت. نه لزوما مستقیم). ارتباط با دنیای خارج از طریق خروجی های مخفی ویژه ای که در برخی از پناهگاه ها قرار دارند انجام می شود.
سازمان باید در مواقع اضطراری برنامه تخلیه کارکنان را تنظیم کند. برای انجام این کار، برای هر یک از پناهگاه ها، باید دریابید که چقدر طول می کشد تا به نزدیک ترین خروجی برسید. به شما به عنوان یک متخصص در چنین وظایفی، دستور داده شده است که زمان مورد نیاز برای هر یک از پناهگاه ها را با توجه به توضیحات داده شده از محل سازمان فوق سری محاسبه کنید. برای راحتی شما، پناهگاه ها از
1 تا
N شماره گذاری شده اند.
ورودی:
- دو خط اول شامل دو عدد طبیعی
N،
K (
\(1 <= N <= 100000\) است. ،
\(1 <= K <= N\)) — تعداد پناهگاه ها و تعداد خروجی ها به ترتیب؛
- در خط سوم، اعداد مختلف
K از
1 تا
N را با فاصله از هم جدا کرده و شماره پناهگاه‌هایی را که خروجی‌ها در آن قرار دارند، نشان می‌دهد.
- خط چهارم حاوی عدد
M (
\(1 <= M <= 100000\)) — تعداد تونل ها؛
- در
M زیر خطوط جفت اعداد را وارد می کنند – تعداد پناهگاه هایی که توسط یک تونل به هم متصل شده اند.
هر یک از تونل ها می توانند در هر دو جهت حرکت کنند. یک سازمان تونل هایی ندارد که از یک پناهگاه به سمت خود منتهی می شود، اما می تواند بیش از یک تونل بین یک جفت پناهگاه وجود داشته باشد.
خروجی: چاپ
N اعداد جدا شده با فاصله — برای هر یک از پناهگاه ها، حداقل زمان لازم برای رسیدن به خروجی. فرض کنید زمان سفر از طریق یک تونل
1 است.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3
1
2
3
1 2
3 1
2 3
| 1 0 1 |
| 2 |
10
2
10 8
9
67
75
58
8 1
1 10
10 3
34
49
9 2 |
1 4 1 2 1 3 2 0 3 0 |