Коровы отправлены в космос за новой доильной машиной для коровника. Они летят через звёздное скопление с $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