Problem
N시에서는 불확실한 상황에서 공장 중 하나의 영토가 변칙 구역으로 변했습니다. 영토의 모든 입구가 막혔고 그 자체를 산업 지대라고 불렀습니다. 산업단지에는
N개의 건물이 있으며 그 중 일부는 도로로 연결되어 있습니다. 모든 도로는 양방향으로 이동할 수 있습니다.
초보 스토커는 산업 구역의 창고에 도착하는 임무를 받았습니다. 그는 전자 기록 보관소에서 산업 지대 영토의 여러 지도를 발견했습니다. 지도는 다른 사람들에 의해 편집되었기 때문에 각 지도에는 산업 지역의 일부 도로에 대한 정보만 포함되어 있습니다. 같은 도로가 여러 지도에 나타날 수 있습니다.
도중에 스토커는 아카이브에서 휴대폰으로 하나의 카드를 다운로드할 수 있습니다. 새 지도를 다운로드하면 이전 지도는 휴대폰 메모리에 저장되지 않습니다. 스토커는 현재 로드된 지도에 표시된 도로를 따라서만 이동할 수 있습니다. 각 지도 다운로드 비용은 1루블입니다. 비용을 최소화하기 위해 스토커는 지도를 가능한 한 적게 다운로드하기 위해 이러한 경로를 선택해야 합니다. Stalker는 동일한 지도를 여러 번 다운로드할 수 있으며 다운로드할 때마다 비용을 지불해야 합니다. 처음에는 휴대폰 메모리에 카드가 없습니다.
스토커가 공업단지 입구에서 창고까지 가는 데 필요한 최소한의 비용을 계산하는 프로그램을 작성해야 합니다.
입력:
- 입력의 첫 번째 줄에는 두 개의 자연수
N 및
K가 포함됩니다(
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) — 공업지대 건물의 수와 지도의 수. 산업단지 입구는 숫자가
1인 건물과 창고 — 건물 번호
N에서.
- 다음 줄에는 사용 가능한 카드에 대한 정보가 있습니다.
i번째 카드 설명의 첫 줄에는
ri 숫자가 포함되어 있습니다.
i번째 지도에 표시된 도로의 수;
- 그런 다음 두 개의 자연수
a 및
b를 포함하는
ri 문자열이 나옵니다(
\(1 <= a\),
\(b <= N\);
\(a ? b\)), 건물
a와
b<를 연결하는 i 지도에 도로가 있음을 의미합니다. /코드>. 모든 지도에 표시된 도로의 총 개수는 300,000개를 초과하지 않습니다(\(r_1 + r_2 + … + r_K <= 300,000\)).
출력: 단일 숫자 인쇄 — 스토커 비용의 최소 금액. 창고에 갈 수 없는 경우 숫자 –1을 인쇄하십시오.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
12 4
4
16
24
79
10 12
3
14
7 11
36
3
25
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |