시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 128 MB87528322234.579%

문제

한국에 처음 도착한 미국인 Mr.Goofcode는 한국의 수도 서울을 여행할 생각에 들떠 있었다. 하지만, 공항 철도를 타고 서울역에 도착한 Mr.Goofcode는 복잡한 서울의 지하철 노선도를 보고 경악을 금치 못했다. 왜냐하면, 서울역을 포함한 서울의 모든 역은 이름이 아닌 숫자로 구분해야 했으며, 운영되는 지하철의 종류(호선)가 너무 많아 최적의 이동 경로를 계산하기 어려웠기 때문이다.

Mr.Goofcode는 패닉에 빠져 평소 메일로 편지를 주고 받던 당신에게 도움을 요청했다. 평소 Mr.Goofcode에게 도움을 받았던 당신은 그를 위해 지하철 노선도 어플리케이션을 만들어 주려고 한다. 그러나, 까다로운 Mr.Goofcode는 걷는 것을 매우 싫어한다. 따라서, 그를 위해 가능하면 어플리케이션이 제시하는 지하철 환승 횟수를 최소로 줄이고 싶어 한다.

Mr.Goofcode를 위해 주어진 지하철 노선도를 보고 Mr.Goofcode가 목적지에 도달하기 위해 최소 몇 번의 환승이 필요한지 구해주자. 단, Mr.Goofcode의 출발역인 서울역의 역 번호는 항상 0번이다.

지하철의 '호선'이란 한 종류의 지하철에서, 다른 지하철로 환승하지 않고 이동할 수 있는 역의 집합을 의미한다. 지하철의 '역'이란 지하철의 호선의 원소로 지하철이 방문할 수 있는 정점을 의미한다. 각 역은 간선으로 연결 관계를 나타낼 수 있으며, 이 간선을 통해서만 지하철이 이동할 수 있다. 지하철은 양 방향으로 이동할 수 있다.

입력

첫째 줄에 서울의 지하철 호선의 개수 N(1 ≤ N ≤ 10)이 주어진다.

둘째 줄부터, 순서대로 1호선부터 N호선까지, 각 호선의 역 개수 K(1 ≤ K ≤ 10)와 각 지하철 호선이 포함하는 역의 번호aN1, aN2, aN3, ... aNK가 한 줄에 주어진다. 각 역의 번호는 모두 다르며 0이상 232-1 이하의 정수임이 보장되어 있다.

입력의 마지막 줄에는, 도착역의 번호가 주어진다.

각 지하철 호선 중, 순환선이 있을 수 있음에 주의하자, 순환선의 입력은 호선이 포함하는 역의 번호가 a1, a2, a3, ... aK-1, a1 의 꼴로 주어진다. (예제 2번)

출력

출발 역(서울 역)에서 도착 역까지 최소 환승 횟수를 한 줄에 출력한다. 단, 도달할 수 없는 경우 -1을 출력한다.

예제 입력 1

3
3 0 2 3
4 2 5 7 10
2 10 8
8

예제 출력 1

2

서울의 지하철 노선은 총 3개이다. 1호선에는 0, 2, 3번 역이 있고, 2호선에는 2, 5, 7, 10번 역이 있고, 3호선에는 10, 8번 역이 있다.

출발역인 0번 역에서 8번 역으로 가는 최소 환승 회수는 (호선, 역)의 경로로 나타내면 (1, 0)-(1, 2)-(2,2)-(2,5)-(2,7)-(2,10)-(3,10)-(3,8)로

최소 2번의 환승을 해야 0번역에서 8번역으로 이동할 수 있다.

예제 입력 2

3
4 1 2 3 1
5 0 9 4 7 99
4 8 10 7 9
1

예제 출력 2

-1

1호선은 순환선이다. 따라서 한 역의 번호가 중복될 수 있다.

출처

University > 숭실대학교 > 2018 SCAL-MOOKJA B번

University > 중앙대학교 > 2018 SCAL-MOOKJA B번