스토커
면접 대비시간 제한2초메모리 제한1024 MB
N개 건물과 K개의 지도가 주어질 때, 지도를 몇 번 내려받아야 1번 건물에서 N번 건물까지 갈 수 있는지 최소 횟수를 구한다. 처음에는 지도가 없다.
문제
도시 N에서 정체불명의 사건으로 공장 하나의 부지가 이상 구역으로 변했다. 부지로 통하는 모든 진입로가 막혔고, 그곳은 산업 구역이라 불리게 되었다. 산업 구역에는 N개의 건물이 있고, 일부 건물은 도로로 연결되어 있다. 어떤 도로든 양방향으로 이동할 수 있다.
초보 스토커가 산업 구역의 창고까지 가라는 임무를 받았다. 그는 전자 문서고에서 산업 구역의 지도 여러 장을 찾았다. 지도마다 만든 사람이 달라서 각 지도에는 산업 구역의 도로 중 일부만 표시되어 있다. 같은 도로가 여러 지도에 있을 수 있다.
이동 중 스토커는 문서고에서 휴대폰으로 지도를 한 장씩 내려받을 수 있다. 새 지도를 내려받으면 휴대폰 메모리에 있던 이전 지도는 남지 않는다. 스토커는 현재 내려받은 지도에 표시된 도로로만 이동할 수 있다. 지도를 한 번 내려받을 때마다 1루블을 지불한다. 비용을 줄이려면 스토커는 지도를 내려받는 횟수가 최대한 적도록 경로를 정해야 한다. 같은 지도를 여러 번 내려받아도 되고, 그때마다 요금을 낸다. 처음에는 휴대폰 메모리에 아무 지도도 없다.
산업 구역 입구에서 창고까지 가는 데 필요한 최소 비용을 계산하는 프로그램을 작성해야 한다.
입력
첫 줄에 자연수 N과 K가 주어진다 (2 ≤ N ≤ 2000, 1 ≤ K ≤ 2000). 각각 산업 구역의 건물 수와 지도 수이다. 산업 구역 입구는 1번 건물에 있고 창고는 N번 건물에 있다.
다음 줄들에는 보유한 지도에 대한 정보가 있다. i번째 지도 설명의 첫 줄에는 i번째 지도에 표시된 도로의 수 ri가 있다. 그다음 ri개 줄에 자연수 a와 b가 주어진다 (1 ≤ a, b ≤ N, a ≠ b). 이는 i번째 지도에 건물 a와 b를 잇는 도로가 있음을 뜻한다. 모든 지도에 표시된 도로 수의 합은 300 000을 넘지 않는다 (r1 + r2 + … + rK ≤ 300 000).
출력
스토커의 최소 비용을 한 줄에 출력한다. 창고에 도달할 수 없으면 -1을 출력한다.