- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شایان مقادیر زیادی به بهنود بدهکار است.(مقدار زیادی وجه نقد، زمین‌های شمال مکزیک و بخش قابل توجهی از نفت خاورمیانه) و به همین علت تمام تلاشش را می‌کند تا با او مواجه نشود.
آن‌ها در شهری زندگی می‌کنند که به شکل یک گراف $n$ راسی و $m$ یالی است. شایان در ابتدا در راس $S$ است و می‌خواهد به راس $T$ که حمیدرضا در آنجا انتظارش را می‌کشد برود تا با او تنیس بازی کند(حمیدرضا خیلی اهل فوتبال نیست)
همزمان که شایان به سمت راس $T$ می‌رود، بهنود نیز که از اینکه نتوانسته طلبش را وصول کند، افسرده و پریشان شده با سرعتی برابر شایان گشتی مشخّص را با هدفی نامشخص طی می‌کند.(هر دو همزمان شروع به حرکت می‌کنند و برایشان طی کردن هر یال ۱ ثانیه زمان می‌برد) شایان کاملا مسیری که بهنود طی می‌کند را می‌داند، و سعی می‌کند گشتی را انتخاب کند که در هیچ کجای آن بهنود را نبیند٬ همچنین شایان می‌تواند در ۱ ثانیه در یک راس ثابت بماند و حرکت نکند یا در یک راس چند بار برود اما مسیر بهنود کاملا ساده است. (دقت کنید که شایان ممکن است بهنود را در یک راس یا در یک یال ببیند، در صورتی که هر دو همزمان در حال طی کردن آن یال باشند.)
او منطقا کوتاه‌ترین گشتی از $S$ به $T$ که شرط بالا را دارد طی می‌کند، اما قبل از حرکت از شما می‌خواهد که به او بگویید، طول این گشت چقدر است یا بگویید چنین گشتی وجود ندارد.
ورودی
در سطر اول ورودی دو عدد $n$ و $m$ و در سطر بعد دو عدد $S$ و $T$ آمده‌است.
در $m$ سطر بعد هر خط، دو عدد $u$ و $v$ آمده است، که به معنی وجود یالی بی جهت از راس $u$ به راس $v$ می‌باشد.
در سطر بعدی عدد $k$ و در ادامه $k$ عدد آمده است که عدد $i$ام برابر با راس $i$ام مسیر بهنود است.
$$1 \le n, m \le 1\ 000\ 000$$ $$1 \le s, t, u, v, k \le n$$ $$1 \le u , v \le n$$
- تضمین می‌شود گراف ساده است.
خروجی
در تنها سطر خروجی، طول کوتاه ترین گشت با شرط گفته شده در صورت سوال را چاپ کنید. اگر چنین گشتی وجود ندارد، -1 چاپ کنید.
زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۳۱ | $n, m \le 2\ 000$ |
| ۴ | ۶۹ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
3 3
1 3
1 2
2 3
3 1
2
3 1
خروجی نمونه ۱
2
ارسال پاسخ برای این سؤال