거쳐 가는 언어의 수

문제

5 3 2
1 2 3
3 4 5

3

10 4 3
10 1 9 8
1 3 6 8
2 3 5 10

2

3 2 2
2 1
1 2

-1

입력 조건

• 가장 먼저 언어의 수 N과 사전 한 권이 다루는 언어의 수 K, 그리고 사전의 수 M이 공백으로 구분되어 한 줄에 주어진다. N은 100,000보다 작거나 같은 자연수이며, K와 M은 각각 1,000보다 작거나 같은 자연수다.

• 이어서 M개의 줄에 걸쳐 1번 사전부터 M번 사전까지 각 사전이 다루는 언어의 번호가 공백으로 구분되어 차례대로 주어진다. 언어의 번호는 1 이상 N 이하의 자연수이며, 한 줄에 적히는 번호의 개수는 K개를 넘지 않는다. 입력에 적히는 언어 번호의 총 개수는 1,000,000개를 넘지 않는다.

출력 조건

• 문서가 거치는 언어의 최소 개수를 한 줄에 출력한다. 처음의 1번 언어와 마지막의 N번 언어도 함께 센 값이다. 1번 언어에서 N번 언어로 갈 길이 없다면 -1을 출력한다. 수 하나만 출력하므로 줄 끝에 남기는 공백은 없다.

요구사항

• 한 사전이 다루는 언어끼리는 한 번의 작업으로 서로 옮길 수 있습니다
• 답은 문서가 거친 언어의 개수이므로, 처음의 1번 언어와 마지막의 N번 언어도 함께 셉니다
• N이 1이면 처음 언어와 마지막 언어가 같으므로 답은 1입니다
• N번 언어로 갈 길이 없다면 -1을 출력합니다
• 언어와 사전을 모두 하나의 점으로 보고 이어 붙이면 점의 개수가 최대 101,000개가 됩니다
• 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
• 쓸 수 있는 말은 파이썬, 자바스크립트입니다
• 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
• 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
• 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
• 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
• 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
• 케이스 15개를 전부 통과해야 해결입니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

3 2 2
2 1
1 2

-1

10 4 3
10 1 9 8
1 3 6 8
2 3 5 10

2

5 3 2
1 2 3
3 4 5

3