+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *شرلوک نامه‌ای از یکی از دوستانش دریافت می‌کند. متن نامه چنین می‌گوید: «شرلوک عزیز، امیدوارم این نامه به موقع به دستتان برسد. من در یک شهر کوچک واقع در سواحل آنتارکتیکا گیر کرده‌ام. قبلا از مسیری گذشته‌ام و دوباره به این شهر رسیده‌ام. اکنون نمی‌دانم از چه مسیری عبور کنم و گم شده‌ام. لطفا سریعا به من کمک کنید. با تشکر، هالیس.»* شرلوک با بررسی دقیق متوجه می‌شود که بعضی از شهرهای آنتارکتیکا با یک جاده به هم متصل هستند و از هر شهر می‌توان با طی کردن تعدادی جاده به هر شهر دیگر رفت. همچنین او یافته است شهری که هالیس در آن قرار دارد متعلق به یک **دور در گراف** آنتارکتیکا است. این گراف بدین گونه ساخته می‌شود: شهرهای آنتارکتیکا رئوس گراف هستند و اگر بین دو شهر جاده ای وجود داشته باشد بین رئوس متناظر آنها یال است. اگر شهر هایی که روی دور قرار دارند را شهرهای حلقوی بنامیم (رئوسی که متعلق به دور هستند)، کوتاه ترین مسیر از شهر فعلی شرلوک به یک شهر حلقوی را چاپ کنید. اگر چند جواب برای مسئله وجود داشت، یکی از آنها را به دلخواه انتخاب کنید. # ورودی ورودی شامل $ m + 3 $ خط است. در خط اول، $k$، شماره شهری که شرلوک در آن قرار دارد می‌آید. در خط دوم، $n$ که تعداد شهرها را نشان می‌دهد آمده است. در خط سوم عدد $m$ داده می‌شود. در $m$ خط بعدی، در هر خط دو عدد با فاصله از هم آمده است که شماره شهرهایی که بین آن‌ها جاده وجود دارد آمده است. <details class="red"> <summary> **نکته: تضمین می‌شود گراف داده‌شده حداکثر $n+1$ یال داشته باشد و شهری که شرلوک روی آن قرار دارد روی دور نباشد.** </summary> </details> $$4 \le n, m \le 100$$ # خروجی در خروجی، کوتاه ترین مسیری که شرلوک را به یک شهر حلقوی می‌رساند چاپ کنید. در صورت وجود چند مسیر، یکی از آنها به دلخواه چاپ شود. # مثال ## ورودی نمونه ۱ ``` 5 6 6 1 2 1 3 2 3 3 4 4 5 5 6 ``` ## خروجی نمونه ۱ ``` 5 4 3 ``` <details class="yellow"> <summary> **توضیحات نمونه ۱** </summary> ----------  اگر گراف را رسم کنیم، می‌بینیم که یک دور با رئوس ۱، ۲ و ۳ داریم و کوتاه‌ترین مسیر از رأسی که شرلوک روی آن قرار دارد (رأس ۵) به نزدیک‌ترین رأس دور (رأس ۳) مسیر زیر می‌باشد: 5 4 3 </details> ## ورودی نمونه ۲ ``` 5 8 9 1 2 1 3 2 3 3 4 4 7 4 8 7 8 4 5 5 6 ``` ## خروجی نمونه ۲ ``` 5 4 ``` <details class="yellow"> <summary> **توضیحات نمونه ۲** </summary> ----------  اگر گراف را رسم کنیم، می‌بینیم که یک دور با رئوس ۱، ۲و ۳ و یک دور با رئوس ۴، ۷ و ۸ داریم و کوتاه‌ترین مسیر از رأسی که شرلوک روی آن قرار دارد (رأس ۵) به نزدیک‌ترین رأس نزدیک‌ترین دور (رأس ۴) مسیر زیر می‌باشد: 5 4 کوتاه‌ترین مسیر به دور دیگر طول ۲ دارد که از مسیر انتخابی ما که طول ۱ دارد بلند‌تر است پس انتخاب ما دور ۴، ۷ و ۸ می‌باشد. </details>

حل سؤال در بانک سؤالات