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