הפרות נשלחו למשימה בחלל להשיג מכונת חליבה חדשה לרפת. הן טסות בצביר כוכבים המכיל $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