부품 확보
면접 대비시간 제한1초메모리 제한1024 MB
행성마다 주어진 한 방향 교환 규칙으로 물건 1을 물건 K로 바꾸는 최소 교환 횟수와 교환 순서를 구합니다.
문제
소들은 외양간에서 쓸 새 착유기를 구하려고 우주를 거쳐 임무를 떠났다. 소들은 각각 교역소가 있는 N개(1 ≤ N ≤ 50,000)의 행성이 모인 성단을 지나고 있다.
소들은 성단의 각 행성이 K종류(1 ≤ K ≤ 1,000)의 물건(1..K 번호) 중 무엇을 원하는지, 그리고 어떤 상품을 교환해야 하는지 알아냈다. 행성에는 화폐가 없어서 물물교환으로 거래한다. 모든 거래에서 양측은 물건을 정확히 하나씩 맞바꾼다(물건의 종류는 서로 다를 것으로 보인다).
소들은 지구에서 고품질 건초 한 통(물건 1)을 들고 출발했고, 새 착유기(물건 K)를 얻고자 한다. 성단의 행성에서 일련의 거래를 거쳐 물건 K를 얻는 가장 좋은 방법을 찾아라. 이 작업이 불가능하면 -1을 출력하라.
입력
첫 줄에 공백으로 구분된 두 정수 N과 K가 주어진다.
i+1번째 줄(1 ≤ i ≤ N)에는 공백으로 구분된 두 정수 a_i와 b_i가 주어진다. 행성 i는 물건 a_i를 받는 대가로 물건 b_i를 준다.
출력
첫 줄에는 물건 K를 얻는 데 필요한 최소 거래 횟수에 1을 더한 값을 출력한다. 물건 K를 얻을 수 없으면 -1을 출력한다.
2번째 줄부터 T+1번째 줄까지는 거래 순서대로 소들이 가지고 있던 물건을 출력한다.
힌트
소들이 가진 물건은 모두 4개다. 먼저 물건 1을 물건 3과 바꾸고, 다음으로 물건 3을 물건 2와 바꾸며, 마지막으로 물건 2를 물건 5와 바꾼다.