+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو و گورو به مشکل خورده اند. داستان از جایی شروع شد که عمو از حیاط خانه شان یه درخت $n$ راسی کند و شروع به بررسی درختش کرد و متوجه شد که هر یال درختش دو حالت دارد :باز یا بسته. در ابتدا تمام یال های درخت باز بودند. او که از این قابلیت درختش شگفت زده شده بود درخت را پیش گورو برد تا باهم بازی کنند. گورو که خوشبختی رو تو تک پر بودن میدید یک مهره روی راس 1 درخت گذاشت و این بازی را روی درخت تعریف کرد: در هر نوبت بازی ، اگر در حال حاضر مهره روی یک راس با درجه 1 بود ، گورو برنده بازی می شود. در غیر این صورت ابتدا عمو یکی از یال های باز درخت را انتخاب و آن را می بندد. اگر تمام یال های درخت بسته بودند، کاری انجام نمی دهد. سپس نوبت گورو می شود. گورو در نوبت خود می تواند یکی از یال های باز متصل به راسی که مهره در آن قرار دارد را انتخاب کند و مهره به سر دیگر این یال ببرد. اگر که هیچ یک از یال های متصل به راس شامل مهره باز نبودند، عمو برنده بازی می شود. عمو که بعد از چند دست بازی همه را شکست خورده بود عصبانی شد و بعد از بحث با گورو مکان را ترک کرد. حالا که آرامشش را به دست آورده است به شما اطلاعات درخت را می دهد و از شما می پرسد که در صورتی که هر دو نفر بهینه بازی می کردند، چه کسی برنده بازی میشد؟ # ورودی خط اول ورودی شامل عدد $n$ ، تعداد رئوس درخت است. در هر یک از $n - 1$ خط بعدی ، دو عدد $u , v$ آمده است که نشانگر وجود یال بین رئوس $u$ و $v$ در درخت است. # خروجی در صورت بهینه بازی کردن دو نفر ، اگر گورو بازی را می برد 1 و اگر عمو بازی را می برد 0 خروجی دهید. # محدودیت ها $$ 1 \leq n \leq 10^5 $$ $$ 1 \leq u , v \leq n $$ ## ورودی نمونه ۱ ``` 6 1 2 2 3 2 4 1 5 5 6 ``` ## خروجی نمونه ۱ ``` 0 ``` عمو می تواند ابتدا یال بین رئوس 1 و 2 را ببندد. در این صورت گورو مجبور است مهره را به راس 5 ببرد. از آنجایی که درجه 5 بیشتر از 1 است ، پس بازی ادامه پیدا می کند. در این مرحله عمو می تواند یال بین رئوس 5 و 6 را ببندد و گورو را مجبور کند تا مهره را به راس 1 برگرداند. سپس با بستن یال بین رئوس 1 و 5 برنده بازی شود. زیرا گورو دیگر نمی تواند مهره را جابجا کند. در نتیجه عمو بازی را می برد. ## ورودی نمونه ۲ ``` 7 1 2 2 3 2 4 1 5 5 6 5 7 ``` ## خروجی نمونه ۲ ``` 1 ``` در این مثال عمو به هر نحوی بازی کند، گورو می تواند مهره را به یک راس درجه 1 برساند. در نتیجه گورو برنده می شود.

حل سؤال در بانک سؤالات