← 返回题目
题库练习 [COCI-2012_2013-contest5]#2 HIPERCIJEVI
← 上一题 下一题 →

A1272 | [COCI-2012_2013-contest5]#2 HIPERCIJEVI

来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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?

输入格式

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.

输出格式

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.

输入输出样例

输入 #1
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9
输出 #1
4
输入 #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
输出 #2
3
C++ 编辑器
输入
输出