تیم ایران تصمیم گرفته است که بعد از مسابقه‌ی جهانی یک مسافرت گردشی برای اعضای تیم خود ترتیب دهد. قرار است که بچه‌ها از یک شهر مبدا شروع به حرکت کرده به شهر مقصد مسافرت کنند و دوباره به شهر مبدا بازگردند. چون وقت بچه‌های تیم خیلی ارزش دارد آن‌ها انتظار دارند که کم‌ترین مقدار از وقت خود را صرف دیدن مناطق تکراری بکنند. بنابراین انتظار می‌رود که مسیر رفت تا شهر مقصد و مسیر برگشت تا شهر مبدا کم‌ترین تعداد جاده‌ی مشترک را داشته باشند.

شما باید برنامه‌ای بنویسید که این دو مسیر را بیابد.

در سطر اول فایل ورودی $S$ و $D$ شماره‌ی شهرهای مبدا و مقصد مشخص شده است. در سطر دوم دو عدد $M$ و $N$ داده شده است که $N$ تعداد شهرها و $M$ تعداد جاده‌ها بین شهرها را مشخص می‌کند. شهرها از ۱ تا $N$ شماره‌گذاری شده‌اند. در $M$ سطر بعدی در هر سطر دو عدد $P$ و $Q$ وجود دارد که $(1\leq P,Q \leq N,P <> Q)$ و مشخص می‌کند که یک جاده‌ی دو طرفه بین شهر‌های $P$ و $Q$ کشیده شده است. بین هر دو شهر حداکثر یک جاده کشیده شده است. در ضمن $3\leq N \leq 1000$ و $2\leq M \leq 10^5$.

در سطر اول فایل خروجی شما باید کم‌ترین تعداد جاده‌ی مشترک بین دو مسیر رفت و برگشت را بنویسید. سطر دوم باید مسیر رفت به صورت دنباله‌ای که حاوی شهر مبدا و مقصد است نوشته شود. در سطر سوم شما باید مسیر برگشت را نیز به صورت دنباله‌ای که حاوی شهر مبدا و مقصد است بنویسید. اگر چند جفت مسیر با کم‌ترین تعداد جاده‌ی مشترک وجود دارد شما می‌توانید هر کدام را در خروجی بنویسید. اگر هیچ مسیری از شهر مبدا به مقصد وجود ندارد شما باید در اولین و تنها سطر فایل خروجی عدد ۱- را بنویسید.

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