| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT134D - Di chuyển trong thiên hà |
In a galaxy far, far away, the fastest method of transportation is using hypertubes. Each hypertube directly connects K stations with each other. What is the minimum number of stations that we need to pass through in order to get from station 1 to station N?
Input
The first line of input contains three positive integers: N (1 <= N <= 100 000), the number of stations, K (1 <= K <= 1 000), the number of stations that any single hypertube directly interconnects, and M (1 <= M <= 1 000), the number of hypertubes.
Each of the following M lines contains the description of a single hypertube: K positive integers, the labels of stations connected to that hypertube.
Output
The first and only line of output must contain the required minimum number of stations. If it isn't possible to travel from station 1 to station N, output -1.
Example
Input:
Input 1:
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9
Input 2:
15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13
Output:
Output 1:
4
Output 2:
3
Clarification of the first example: It is possible to travel from station 1 to station 9 using only four stations in the following ways: 1-3-6-9, or 1-5-6-9.
| Được gửi lên bởi: | adm |
| Ngày: | 2013-02-26 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
