المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۲۰:عملی:سوال ۱

درخت بازی

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

ابزار صفحه