در یک کشور ‎$n$‎ جاسوس خارجی فعالیت می‌کنند. به دلیل محدودیت‌های مخابراتی و لزوم حفظ امنیت، هر جاسوس تنها با بعضی از سایر جاسوسان می‌تواند ارتباط مستقیم برقرار کند. هر جاسوس یک درجه‌ی رازداری دارد که بر اساس خدماتی که انجام می‌دهد این درجه افزایش می‌یابد. هنگامی که یک جاسوس (مثل ‎$s$‎) بخواهد پیامی را به جاسوس دیگر (مثل ‎$t$) بفرستد اگر بتواند از ارتباط مستقیم استفاده می‌کند، در غیر این صورت ناچار خواهد بود مسیری از جاسوسان میانی را انتخاب کند تا پیام بین آن‌ها دست به دست شود و به مقصد برسد. اما انتخاب مسیر باید به گونه‌ای باشد که بالاترین ضریب امنیت برای انتقال پیام تامین شود. ضریب امنیت هر مسیر معادل است با کمینه درجه‌ی رازداری جاسوسان قرار گرفته در طول ان مسیر، از جمله جاسوس ارسال کننده‌ی پیام و جاسوس مقصد.

برنامه‌ای بنویسید که با دریافت اطلاعات شبکه‌ی جاسوسی، مسیر انتقال پیام با بالاترین ضریب امنیت را پیدا کند یا عدم وجود چنین مسیری را گزارش نماید.

• در سطر اول ابه ترتیب اعداد ‎$n$‎، ‎$s$‎، ‎$t$‎ و ‎$m$‎ آمده‌اند. فرض کنید ‎$n\leq 10^4$‎ و ‎$m \leq 10^5$‎.
• در سطر دوم ‎$n$‎ عدد طبیعی آمده‌اند که عدد ‎$i$‎ام نشان‌دهنده‌ی درجه‌ی رازداری جاسوس ‎$i$‎ام است. هیچ یک از این اعداد از ‎$10^6$‎ بیشتر نیست.
• در ‎$m$‎ سطر بعدی در هر سطر یک جفت ‎$u$‎ و ‎$v$‎ آمده است که نمایانگر یک امکان ارتباط مستقیم بین جاسوس‌های شماره‌ی ‎$u$‎ و ‎$v$‎ است. ارتباط مستقیم تکراری در ورودی نمی‌آید.

• اگر هیچ راهی برای ارسال پیام وجود ندارد فقط بنویسید ‎impossible‎.
• در غیر این‌صورت در سطر اول ابتدا ضریب امنیت مسیر و سپس تعداد جاسوسان در طول مسیر (از جمله $s$‎ و ‎$t$‎) را بنویسید و در سطر دوم جاسوسان قرار گرفته روی مسیر از ‎$s$‎ به ‎$t$‎ را به ترتیب بنویسید.
• اگر چند مسیر با ضریب امنیت یکسان وجود داشت می‌توانید هر یک از آن‌ها را بنویسید. این مسیر نباید شامل افراد تکراری باشد.

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

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

‎‎