Judge - KoreaTech 최고의 사랑 노선을 찾아

문제 설명

KoreaTech 대회 창사 이래로 5년 넘게 솔로로 지내온 종욱이는 KoreaTech 컴퓨터공학부 광장을 걷던 중, 엄청난 대자보를 보게 되었습니다.

"솔로에게 축복이! KoreaTech 최고의 사랑 노선 찾기 이벤트!!"
해당 대자보의 제목은 위와 같았고 그 내용은 아래와 같았습니다.

솔로로 20년 넘게 지내온 당신! 솔로의 신의 경지에 이르러 눈빛만으로도 천지 만물을 창조하기에 이른 당신에게 솔로 탈출의 축복을 드리는 이벤트를 개최합니다.
단, 아래의 조건을 만족해야만 여러분께 이벤트 축복을 행사해 드린다는 점! 명심해 주세요.

지금 우리는 특정 출발지와 목적지가 주어졌을 때 가장 효과적인 경로로 이동하는 방법을 찾고 있습니다.
즉, 각각의 버스 노선이 주어졌을 때 출발지에서 목적지까지 가는 데에 필요한 최소한의 버스 개수를 찾아주세요.
단, 출발지에서 목적지까지 갈 방법이 없으면 -77을 출력해 주세요.

오..!! KoreaTech 제군 여러분.. 올해에는 기필코 솔로 탈출을 다짐한 종욱이에게 도움의 손길을 주세요.

입력 설명

첫 줄에는 테스트케이스 T(1 ≤ T ≤ 10³)가 주어집니다.
각 테스트케이스 첫 줄에는 총 버스 노선 수 B(1 ≤ B ≤ 10³)가 주어집니다. 그다음 줄에는 노선 수 마다 두 줄로 노선 정보가 주어집니다. 노선 정보의 첫 줄에는 버스 Bi가 지나가는 버스 정류장의 개수 A(1 ≤ A ≤ 10³)가 주어지며, 둘째 줄에는 A개의 정류장 번호 N(1 ≤ N≤ 10⁶)이 주어집니다.
그후 마지막 두줄에 시작점인 S와 도착지점인 D가 주어집니다. (S와 D는 반드시 테스트케이스에 주어진 버스 노선 중 어딘가에 포함되어 정류장 번호입니다.)

출력 설명

각 줄에는 출발지에서 목적지까지 도달하는데 필요한 최소한의 버스 수를 출력합니다.
단, 출발지에서 목적지에 도달하는 방법이 없으면 -77을 출력합니다.

입력 예시 Copy

3
1
2
300 77
300
77
2
3
303 300 400
4
400 307 404 77
300
77
1
2
300 77
300
17

출력 예시 Copy

1
2
-77

도움

이 문제를 푸는 팀에게는 종욱이가 메로나를 사겠습니다.
종욱이는 올해 솔로를 탈출할 수 있을까요?

1292: KoreaTech 최고의 사랑 노선을 찾아

문제 설명

입력 설명

출력 설명

입력 예시 Copy

출력 예시 Copy

도움

출처/분류