소들은 헛간에 새 착유기를 구하기 위해 우주 임무에 나섰다. 각각 교역소가 있는 행성 $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$번 줄은 행성 $i$의 거래 물건인 두 정수 $a_i$, $b_i$를 공백으로 구분해 포함한다. 행성은 물건 $a_i$를 받는 대가로 물건 $b_i$를 준다.

출력

• 1번 줄: 착유기인 물건 $K$를 얻는 최소 거래 횟수에 1을 더한 값 (물건 $K$를 얻을 수 없으면 -1).
• $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