آقا داوود علاوه‌بر بدن‌سازی در پیش‌گویی نیز از بزرگان زمان خود به حساب می‌آید. او با توجه به وضعیت ستارگان در آسمان به این نتیجه رسیده‌ است که در سال 13920613 جنگ جهانی سوم اتفاق می‌افتد و خسارات فراوانی به بار می‌آید. او می‌داند که در آن سال‌ها کشور‌ها به صورتی در می‌آیند که اگر بخواهیم از روی آن‌ها گرافی بسازیم به این صورت که به ازای هر کشور یک راس در گراف بگذاریم و بین هر دو کشور همسایه یالی وصل کنیم. گراف حاصل تشکیل یک درخت می‌دهد. فاصله‌ دو کشور $A$ و $B$ را مساوی با کوتاهترین مسیر بین این دو کشور در گراف ساخته شده می‌نامیم. هر کشوری تنها دارای یک نوع موشک است که ساخت خود آن کشور نیز هست. هر موشک دارای یک شعاع است به این معنا که فاصله‌ی بین کشور شلیک‌ کننده‌ی آن با کشوری که در آن منفجر می‌شود دقیقا برابر است با شعاع آن. تمامی موشک‌ها مستقل از کشور سازنده‌ی آن‌ها بعد از یک دقیقه به کشور مورد هدف رسیده و منفجر می‌شوند. هم‌چنین می‌دانیم هنگامی که برای اولین بار موشکی در یک کشور منفجر می‌شود، بلافاصله آن کشور به تمامی کشور‌هایی که ‌می‌تواند شلیک کند (کشورهایی که فاصله‌ای برابر با شعاع موشک‌های آن کشور دارند)، شلیک می‌کند. بنابراین برای شروع جنگ تنها کافی است یک کشور موشک‌های خود را شلیک کند که طبق بررسی‌های آقا داوود اگر کشور‌های را با 1 تا $N$ شماره‌گذاری کنیم، کشور شماره‌ی 1 شروع کننده‌ی جنگ است. با گرفتن کشور‌های همسایه و شعاع موشک‌های ساخت هر کشور، تعیین کنید هر کشور چند دقیقه بعد از شلیک کشور‌ 1، مورد اصابت موشک قرار می‌گیرد.

• سطر اول ورودی شامل یک عدد طبیعی، $2 \leq N \leq 10^5$، تعداد کشورها، است.
• سطر دوم شامل $N$ عدد طبیعی، $1 \leq R_1, \cdots, R_N \leq 100$، است که $R_i$ شعاع موشک‌های ساخت کشور $i$-ام را نشان می‌دهد.
• سطر‌های سوم تا $N+1$-ام هر کدام شامل دو عدد طبیعی، $1 \leq A \neq B \leq N$، است که به معنای همسایه بودن کشور‌های $A$ و $B$ است.
• تضمین می‌شود که گراف تشکیل شده بر اساس همسایگی کشورها، درخت است.
• در ۳۰ درصد از ورودی‌ها، $2 \leq N \leq 3000$، است.

تنها سطر خروجی شامل $N-1$ عدد طبیعی است که عدد $i$-ام مساوی $-1$ است اگر کشور‌ $i+1$-ام مورد حمله‌ی هیچ کشوری قرار نگیرد. در غیر این‌صورت عدد $i$-ام برابر با مدت زمان میان اولین شلیک کشور 1 و اولین اصابت موشک به کشور $i+1$ است.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• ورودی نمونه‌ی اول

• ورودی نمونه‌ی دوم

• سوال قبل