بعد از سفر تیم ملی المپیاد کامپیوتر به کشور بلغارستان خبری به آن‌ها رسید که ‎$K$‎ تا از مبتلایان به آنفولانزای خوکی در شهر پلاودیو (همان شهری که المپیاد امسال در آن برگزار شد و تیم المپیاد کامپیوتر در آن هستند) از قرنطینه فرار کرده‌اند و هدفشان مبتلا کردن بقیه مردم به آنفولانزای خوکی است. بعد از شنیدن این خبر، اعضای تیم و همراهان آن‌ها تصمیم گرفتند در اسرع وقت خود را به فرودگاه برسانند و به میهن عزیزمان بازگردند. نقشه شهر پلاودیو به صورت یک گراف ساده با ‎$N$‎ رأس و ‎$E$‎ یال داده شده است. رئوس از ‎۱‎ تا ‎$N$‎ شماره‌گذاری شده‌اند (وزن همه یال‌ها یک است و یال‌ها بدون جهت هستند). تیم المپیاد کامپیوتر در هر ساعت می تواند یک یال را بپیماید و به یکی از رئوس مجاور برود یا در رأسی که در آن بود بماند (توجه کنید که اعضای تیم همیشه با هم هستند). هر بیمار بعلت بیماری در هر ‎$T$‎ ساعت می‌تواند یک یال را بپیماید و به یکی از رئوس مجاور برود یا در همان رأس بماند. خوشبختانه سازمان مبارزه با آنفولانزای خوکی محل فرار هر یک از بیماران را اعلام کرده است و تیم المپیاد هم در همان لحظه‌ای که بیماران شروع به حرکت می‌کنند، شروع به حرکت می‌کنند.

ما می‌خواهیم تیم از مسیری به فرودگاه برود که احتمال وارد شدن به رأسی، همزمان با ورود یک بیمار به آن رأس در طول راه، وجود نداشته باشد. ما حتی می‌خواهیم ممکن نباشد تیم در رأس فرودگاه با یک بیمار مواجه شود. در زمان شروع به حرکت کردن، تیم المپیاد کامپیوتر ایران در رأس ‎۱‎ قرار دارد و بیمار ‎$i$‎ام در رأس ‎$P_i$‎ قرار دارد. فرودگاه نیز در رأس ‎$N$‎ام قرار دارد. شما باید در صورت وجود مسیری برای نجات تیم المپیاد، کوتاه‌ترین مسیر را پیدا کنید.

• در سطر اول ورودی، چهار عدد ‎$N$ (تعداد رئوس نقشه)، ‎$E$ (تعداد یال‌های نقشه)، ‎$K$ (تعداد بیماران) و ‎$T$ (تعداد ساعاتی که طول می‌کشد تا یک بیمار یک یال را بپیماید) به ترتیب داده شده است.
• در سطر دوم ‎$K$‎ عدد آمده است که شماره رئوسی هستند که بیماران در شروع حرکت در آن‌ها قرار دارند.
• در ‎$E$‎ سطر بعد، در هر سطر دو عدد آمده است که دو سر یک یال را نشان می‌دهند.
• ‎$2 \le N \le 50000$‎.
• ‎$0 \le K \le 50000$‎.
• ‎$0 \le E \le 100000$‎.
• ‎$1 \le T \le 10^6$‎

• اگر مسیری برای نجات تیم وجود داشت در سطر اول طول کوتاه‌ترین مسیر و در سطر دوم رئوس یکی از کوتاه‌ترین مسیرها را (شامل رئوس ‎۱‎ و ‎$N$) به ترتیب بنویسید.
• در صورتی که مسیر وجود نداشت در یک سطر بنویسیدimpossible ‎.
• توجه: برنامه‌ی شما برای گرفتن نمره‌ی تست‌هایی که جواب آن‌ها ‎impossible‎ است، می‌بایست حداقل به یکی از تست‌هایی که جواب آن‌ها ‎impossible‎ نیست پاسخ صحیح بدهد.

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

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

‎‎ ‎‎