آقا داوود علاوه‌بر بدن‌سازی در پیش‌گویی نیز از بزرگان زمان خود به حساب می‌آید. او با توجه به وضعیت ستارگان در آسمان به این نتیجه رسیده است که در سال 13920613 جنگ جهانی سوم اتفاق می‌افتد و خسارات فراوانی به بار می‌آید. او می‌داند که در آن سال‌ها کشورها به صورتی در می‌آیند که اگر بخواهیم از روی آن‌ها گرافی بسازیم به این صورت که به ازای هر کشور یک راس در گراف بگذاریم و بین هر دو کشور همسایه یالی وصل کنیم. گراف حاصل تشکیل یک درخت می‌دهد. فاصله دو کشور $A$ و $B$ را مساوی با کوتاهترین مسیر بین این دو کشور در گراف ساخته شده می‌نامیم. هر کشوری تنها دارای یک نوع موشک است که ساخت خود آن کشور نیز هست. هر موشک دارای یک شعاع است به این معنا که فاصله‌ی بین کشور شلیک کننده‌ی آن با کشوری که در آن منفجر می‌شود دقیقا برابر است با شعاع آن. تمامی موشک‌ها مستقل از کشور سازنده‌ی آن‌ها بعد از یک دقیقه به کشور مورد هدف رسیده و منفجر می‌شوند. هم‌چنین می‌دانیم هنگامی که برای اولین بار موشکی در یک کشور منفجر می‌شود، بلافاصله آن کشور به تمامی کشورهایی که می‌تواند شلیک کند (کشورهایی که فاصله‌ای برابر با شعاع موشک‌های آن کشور دارند)، شلیک می‌کند. بنابراین برای شروع جنگ تنها کافی است یک کشور موشک‌های خود را شلیک کند که طبق بررسی‌های آقا داوود اگر کشورهای را با 1 تا $N$ شماره‌گذاری کنیم، کشور شماره‌ی 1 شروع کننده‌ی جنگ است. با گرفتن کشورهای همسایه و شعاع موشک‌های ساخت هر کشور، تعیین کنید هر کشور چند دقیقه بعد از شلیک کشور 1، مورد اصابت موشک قرار می‌گیرد.
تنها سطر خروجی شامل $N-1$ عدد طبیعی است که عدد $i$-ام مساوی $-1$ است اگر کشور $i+1$-ام مورد حمله‌ی هیچ کشوری قرار نگیرد. در غیر این‌صورت عدد $i$-ام برابر با مدت زمان میان اولین شلیک کشور 1 و اولین اصابت موشک به کشور $i+1$ است.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 5 2 3 1 2 1 1 2 2 3 3 4 1 5 | 2 1 2 -1 |
| 6 5 3 1 1 2 4 1 2 2 3 3 4 4 5 5 6 | 2 4 5 3 1 |
| کشورهای مورد اصابت موشک | کشورهای شلیک کننده | دقیقه |
|---|---|---|
| - | 1 | 0 |
| 3 | 3 | 1 |
| 2, 4 | 4 | 2 |
| 2 | - | 3 |
| کشورهای مورد اصابت موشک | کشورهای شلیک کننده | دقیقه |
|---|---|---|
| 1 | 0 | |
| 6 | 6 | 1 |
| 2 | 2 | 2 |
| 5 | 5 | 3 |
| 3 | 3 | 4 |
| 5 | 4 | 4 |