درخت بازی

شایان و و مرتضی مشغول یک بازی بسیار بسیار جذاب هستند. آن‌ها بر روی کاغذ، درختی با $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 را بنویسید.

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

• سوال بعد