Graph

گرافی جهت‌دار و بدون‌دور داریم که روی برخی از رئوسش تعدادی مهره قرار دارد. خیکوله و خیکولا روی این گراف به شکل زیر بازی می کنند:

• ‎ هر کس در نوبت خودش با هر کدام از مهره‌ها یک حرکت انجام می‌دهد.
• ‎‎ حرکت دادن یک مهره یعنی آن را به یکی از رئوس خروجی راسی که در آن قرار دارد منتقل کنیم.
• ‎ کسی که نتواند حرکتی انجام دهد بازنده است.

به عبارت دیگر، در هر مرحله، در صورتی که یکی از مهره‌ها روی راسی قرار داشته باشد که هیچ یال خروجی ندارد، کسی که نوبت اوست می‌بازد، در غیر این صورت، آن فرد باید همه‌ی مهره‌ها را یک یال حرکت بدهد. ‎ شما باید برنامه‌ای بنویسید که با گرفتن وضعیت اولیه بازی، با فرض اینکه هر دو بازیکن به شکل بهینه بازی می‌کنند، برنده‌ی بازی را مشخص کند. ‎

• ورودی شامل دقیقا ‎۵‎ سناریوی بازی است که پشت‌سرهم آمده‌اند‎.‎
• در خط اول هر سناریو به ترتیب، ‎$(1 \leq n \leq 10^5)$‎ تعداد رئوس گراف، ‎$(1 \leq m \leq 2 \times 10^5)$‎ تعداد یال‌های آن و ‎$(1 \leq k \leq 10^5)$‎ تعداد مهره‌ها آمده است.
• در خط بعد ‎$k$‎ عدد آمده است که هر کدام نشان دهنده‌ی شماره‌ی راس یکی از مهره‌هاست. (رئوس گراف از ‎$1$‎ تا ‎$n$‎ شماره‌گذاری شده‌اند.)
• در ‎$m$‎ خط بعدی در هر خط به ترتیب ۲‎ عدد ‎$(1 \leq a,b \leq n),(a \neq b)$‎ آمده است که نشان‌گر یک یال از راس ‎$a$‎ به راس ‎$b$‎ می‌باشد.

‎ در خروجی به‌ازای هر سناریو در یک خط یکی از دو عدد ‎$1$‎ یا ‎$2$‎ را چاپ کنید. در صورتی که نفر اول برنده‌ی بازی است، عدد یک و در غیر این صورت عدد دو را چاپ کنید.

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

• سوال بعد
• سوال قبل‎