====== درخت بازی ====== شایان و و مرتضی مشغول یک بازی بسیار بسیار جذاب هستند. آن‌ها بر روی کاغذ، درختی با $n$ راس رسم کرده‌اند (به گراف همبند و بدون دور، درخت گفته می‌شود) که روی $k$ تا از رئوس آن علامت خورده است. هر بازیکن در نوبت خود می‌تواند یکی از برگ‌های درخت را انتخاب کند، آن برگ را مال خود کند و آن برگ و یال متصل به آن را از درخت حذف کند. شخصی که اولین راس علامت خورده را مال خود کند، برنده‌ی بازی است. فرض کنید که شایان بازیکن اول است. ===== ورودی ===== * در سطر ا ول ورودی، $n$ تعداد رئوس گراف ($1\leq n \leq 5\times 10^5$) و $k$ تعداد رئوس علامت خورده ($k\leq n$) با یک فاصله از هم نوشته شده است. * در هر یک از $n-1$ سطر بعد، دو عدد $u$ و $v$($1\leq u,v\leq n$) با یک فاصله از هم آمده‌اند که نشان می‌دهد که یک یال بین راس $u$ام و راس $v$ام وجود دارد. * در $k$ سطر بعد، در هر سطر یک عدد آمده است که شماره‌ی یکی از رئوس علامت خورده را مشخص می‌کند. ===== خروجی ===== در تنها سطر خروجی، اگر شایان (نفر اول) برنده‌ی بازی بود، عبارت ''shayan'' را بنویسید؛ در غیر این صورت عبارت ''morteza'' را بنویسید. ===== محدودیت‌ها ===== * محدودیت زمان: ۵ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |5 2 \\ 1 2 \\ 2 3 \\ 3 4 \\ 3 5 \\ 2 \\ 3 | shayan| * [[سوال ۲|سوال بعد]]