+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون مقدماتی دوم دوره ۲۶ المپیاد کامپیوتر ---------- بازی Pokemon Go در مدت کوتاهی به محبوب‌ترین بازی کشور هکر‌ها تبدیل شده است! با اینکه هکرها به Pokemon Go بسیار علاقه دارند اما همچنان جذاب‌ترین کار برای آن‌ها هک کردن است. ولادمیر لوین (Vladimir Levin)، یکی از خطرناک‌ترین هکر‌های شهر، تعدادی از سرور‌های Pokemon Go را هک کرده و برنامه‌ی تلفن همراه XPokemon را نوشته است که یکی از قابلیت‌های آن اعلام فاصله‌ی دورترین PokeStop از مکان فعلی شخص است. لازم به ذکر است که در کشور هکر‌ها، شهرها و جاده‌های بین آن‌ها‌ تشکیل یک درخت می‌دهند و PokeStop ها همواره در داخل شهر‌ها قرار دارند. کوین میتنیک (Kevin Mitnick)، رقیب قدیمی ولادیمیر، در جدید ترین پروژه‌ی خود موفق به هک کردن تلفن‌های همراه ساکنین برخی از شهر‌ها شده است. کوین از طریق این تلفن‌های همراه هک شده به خروجی برنامه Xpokemon دست یافته و می‌خواهد مکان PokeStop ها را بیابد. کوین برای پیدا کردن مکان PokeStop ها نیاز به کمک شما دارد و به همین منظور اطلاعات به دست آمده را با شما به اشتراک گذاشته است. او به ازای هر شهر‌ مانند $v$ که موفق به هک کردن تلفن‌های همراه ساکنین آن شده است، عدد $d$ را، که فاصله‌ی آن شهر با دورترین PokeStop از آن را نشان می‌دهد، به شما داده است. منظور از فاصله بین دو شهر، کمترین تعداد جاده لازم برای رسیدن از شهر اول به شهر دوم است. به کوین کمک کنید و با توجه به اطلاعاتی که در اختیار دارید، مکان PokeStop ها را حدس بزنید. یک حدس معتبر نباید با اطلاعات داده‌شده تناقضی داشته باشد. در صورتی که هیچ حدس معتبری وجود نداشت، اعلام کنید که اطلاعات داده شده نادرست می‌باشد. # ورودی در خط اول ورودی، دو عدد $n$ و $q$ آمده است که به ترتیب تعداد کل شهر‌‌ها و تعداد شهر‌هایی که کوین موفق به هک کردن تلفن‌های همراه ساکنین آن شده است را نشان می‌دهند. در هر یک از $n-1$ خط بعدی در هر خط دو عدد طبیعی $v$ و $u$ آمده است که نشان‌دهنده‌ی وجود یک جاده بین این دو شهر است. در هر یک از $q$ خط بعدی دو عدد $v$ و $d$ آمده است که نشان می‌دهد فاصله دورترین PokeStop از شهر $v$ برابر $d$ است. **تضمین می‌شود گراف ورودی درخت است و به ازای هر شهر حداکثر یک بار اطلاعات داده می‌شود.** $$ 1 \le q \le n \le 200 \ 000 $$ # خروجی در صورتی که هیچ حدس معتبری وجود ندارد، در تنها خط خروجی عدد $-1$ را چاپ کنید. در غیر این‌ صورت، در تنها خط خروجی حدس خود که شامل یک رشته‌ی $n$ حرفی از 0 و 1 می‌شود را چاپ کنید. 0 بودن حرف ‌$i$ام رشته به این معناست که در شهر $i$ام PokeStop ای وجود ندارد و 1 بودن آن به این معناست که در شهر $i$ام PokeStop وجود دارد. در صورتی که چند جواب برای ورودی داده شده وجود دارد می‌توانید هر کدام را که خواستید چاپ کنید. # زیرمسئله‌ها | زیرمسئله | شماره‌ی تست‌ها| نمره | محدودیت |:------------------:|:--------:|:----------:|:------------------:| | ۱ | ۱ تا ۱۱ | ۱۰ | $ n \le 15 $ | | ۲ | ۱۲ تا ۲۴ | ۲۰ | $ n \le 200 $ | | ۳ | ۲۵ تا ۳۴ | ۲۵ | $ n = q $ | | ۴ | ۳۵ تا ۶۴ | ۴۵ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 4 1 2 1 3 1 4 1 5 2 2 3 2 4 2 5 2 ``` ## خروجی نمونه ۱ ``` 01111 ``` ## ورودی نمونه ۲ ``` 3 3 1 2 2 3 1 0 2 1 3 0 ``` ## خروجی نمونه ۲ ``` -1 ```