أُرسلت الأبقار في مهمة فضائية للحصول على آلة حلب جديدة لحظيرتها. تطير عبر عنقود نجمي يضم $N$ كوكبًا ($1 \le N \le 50{,}000$)، لكل منها مركز تجاري.

حددت الأبقار أيًا من أنواع الأشياء $K$ ($1 \le K \le 1{,}000$)، المرقمة $1..K$، يريد كل كوكب وما المنتجات التي يعرضها. لم يطور أي كوكب عملة، فيستخدمون المقايضة: يبادل كل طرف شيئًا واحدًا بالضبط (يفترض أن النوعين مختلفان).

تنطلق الأبقار من الأرض بعبوة تبن عالي الجودة (الشيء 1)، وتريد آلة حلب (الشيء $K$). أوجد أفضل سلسلة مبادلات على الكواكب للحصول على الشيء $K$. إن استحال ذلك فاطبع -1.

الإدخال

• السطر 1: عددان صحيحان $N$ و$K$ يفصل بينهما فراغ.
• الأسطر $2..N+1$: يحتوي السطر $i+1$ على عددين صحيحين $a_i$ و$b_i$ يفصل بينهما فراغ، وهما منتجات مقايضة الكوكب $i$. يعطي الكوكب الشيء $b_i$ مقابل تلقي الشيء $a_i$.

الإخراج

• السطر 1: أقل عدد مبادلات للحصول على آلة الحلب، الشيء $K$، زائد واحد (أو -1 إن تعذر الحصول على الشيء $K$).
• الأسطر $2..T+1$: قائمة الأشياء التي تمتلكها الأبقار بترتيب المبادلات.

أمثلة

الإدخال 1

6 5
1 3
3 2
2 3
3 1
2 5
5 4

الإخراج 1

4
1
3
2
5

ملاحظة

تفاصيل الإخراج

تمتلك الأبقار 4 أشياء إجمالًا: تبادل أولًا 1 مقابل 3، ثم 3 مقابل 2، ثم 2 مقابل 5.

مؤلفو المسألة: Coaches, 2004