트램
면접 대비시간 제한1초메모리 제한128 MB
각 교차점의 첫 번째 연결은 비용이 0이고 나머지는 비용이 1인 방향 그래프에서, A에서 B까지 가는 데 필요한 최소 스위치 변경 횟수를 구하는 문제입니다.
문제
트램 노선망은 교차로와 교차로를 잇는 선로들로 이루어져 있다. 각 교차로에는 분기기가 하나 있으며, 처음에는 그 교차로에서 나가는 선로 중 하나를 가리키고 있다. 트램이 어떤 교차로에 들어오면 현재 분기기가 가리키는 선로로만 나갈 수 있다. 다른 선로로 나가려면 운전사가 분기기를 직접 바꾸어야 한다.
교차로 A에서 교차로 B로 가야 할 때, 운전사는 직접 분기기를 바꾸는 횟수가 최소가 되는 경로를 선택하려고 한다.
A에서 B까지 이동하는 데 필요한 분기기 변경 횟수의 최솟값을 구하라.
입력
첫째 줄에 정수 N, A, B가 공백으로 구분되어 주어진다. N은 교차로의 개수이며, 교차로는 1번부터 N번까지 번호가 붙어 있다.
2 <= N <= 1001 <= A, B <= N
다음 N개의 줄은 각 교차로에서 나가는 선로를 나타낸다. 이 중 i번째 줄은 정수 K_i (0 <= K_i <= N - 1)로 시작하며, 이는 i번 교차로에서 나가는 선로의 개수이다. 이어서 K_i개의 정수가 주어지며, 각각 i번 교차로에서 직접 갈 수 있는 교차로를 뜻한다.
K_i > 0이면 i번 교차로의 분기기는 처음에 목록의 첫 번째 교차로 방향을 가리키고 있다.
출력
A에서 B로 이동하기 위해 운전사가 직접 바꾸어야 하는 분기기 횟수의 최솟값을 정수 하나로 출력한다.
A에서 B로 가는 경로가 없으면 -1을 출력한다.