بازی Go Pokémon در مدت کوتاهی به محبوب‌ترین بازی کشور هکر‌ها تبدیل شده است! با اینکه هکرها به Go Pokémon بسیار علاقه دارند اما همچنان جذاب‌ترین کار برای آن‌ها هک کردن است. ولادمیر لوین (Levin Vladimir)، یکی از خطرناک‌‌ترین هکر‌های شهر، تعدادی از سرور‌های Go Pokémon را هک کرده و برنامه‌ی تلفن همراه XPokémon را نوشته است که یکی از قابلیت‌های آن اعلام فاصله‌ی دورترین PokéStop از مکان فعلی شخص است. لازم به ذکر است که در کشور هکر‌ها، شهرها و جاده‌های بین آن‌ها‌ تشکیل یک درخت می‌دهند و PokéStop ها همواره در داخل شهر‌ها قرار دارند.

کوین میتنیک (Mitnick Kevin)، رقیب قدیمی ولادیمیر، در جدید ترین پروژه‌ی خود موفق به هک کردن تلفن‌های همراه ساکنین برخی از شهر‌ها شده است. کوین از طریق این تلفن‌های همراه هک شده به خروجی برنامه Xpokémon دست یافته و می‌خواهد مکان PokéStop ها را بیابد.

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

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

در هر یک از $n-1$ خط بعدی در هر خط دو عدد طبیعی $v$ و $u$ آمده است که نشان‌دهنده‌ی وجود یک جاده بین این دو شهر است.

در هر یک از $q$ خط بعدی دو عدد $v$ و $d$ آمده است که نشان می‌دهد فاصله دورترین PokéStop از شهر $v$ برابر $d$ است.

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

در غیر این‌ صورت، در تنها خط خروجی حدس خود که شامل یک رشته‌ی $n$ حرفی از 0 و 1 می‌شود را چاپ کنید. 0 بودن حرف ‌$i$ام رشته به این معناست که در شهر $i$ام PokéStop ای وجود ندارد و 0 بودن آن به این معناست که در شهر $i$ام PokéStop وجود دارد. در صورتی که چند جواب برای ورودی داده شده وجود دارد می‌توانید هر کدام را که خواستید چاپ کنید.

• زیرمسئله اول (۱۰ نمره): $n \le 15$
• زیرمسئله دوم (۲۰ نمره): & $n \le 200$
• زیرمسئله سوم (۲۵ نمره): $q = n$
• زیرمسئله چهارم(۴۵ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le q \le n \le 2 \times 10^5$
• تضمین می‌شود گراف ورودی درخت است.
• تضمین می‌شود به ازای هر شهر حداکثر یک بار اطلاعات داده می‌شود.

• سوال بعد
• سوال قبل