题目描述

在遥远的星系中，最快的运输方式是超级管道，它们将 $K$ 个站台连接在一起。从站台 $1$ 到达站台 $N$ 最少需要经过多少个站台?

输入格式

第一行，三个整数 $N,K,M$，分别表示站台数，每根超级管道连接的站台数和超级管道数。

接下来 $M$ 行，每行 $K$ 个正整数，表示这跟超级管道连接的站台编号。

输出格式

一行，一个正整数，表示最少需要经过的站台数，如果到达不了站台 $N$ ，则输出 -1。

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

4

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

3

提示

【样例解释#1】

有两种方法从站台 $1$ 走到站台 $9$：

$1\Rightarrow 3\Rightarrow 6\Rightarrow 9$ 或 $1\Rightarrow 5\Rightarrow 6\Rightarrow 9$

共经过了 $4$ 个站台，可以证明这是经过站台最少的情况。

【数据范围】

对于 $100\%$ 的数据，$1\le N\le 10^5$，$1\le K,M\le 1000$。

【说明】

本题分值按 COCI 原题设置，满分 $120$。

题目译自 COCI2012~2013 CONTEST#5 T4 HIPERCIJEVI。