问题 D: hipercijevi

问题 D: hipercijevi

时间限制: 1 Sec  内存限制: 128 MB
提交: 857  解决: 171
[状态] [讨论版] [提交] [命题人:]
题目描述

在遥远的星系, 最快的交通方式是用某种管道。 每个管道直接互相连接N个站。 那么我们从第一个站到第N个站最少要经过多少个站呢?

输入

输入文件的第一行为T表示有T组数据

每个数据第一行包含三个正整数 N (1<=N<=100000) 表示站的个数; K (1<=K<=1000) 表示一个管道直接连接了多少个站; M (1<=M<=1000) 表示管道的数量。

接下来的M行, 每行包含一个管道的描述: K个正整数, 表示这个管道连接的K个站的编号。

 

输出

输出文件T行,每行包含一个正整数,表示从第一个站到第N个站最少需要经过多少个站。 如果无法从第一个站到达第N个站,输出-1 

样例输入 Copy
2
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9
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
样例输出 Copy
4
3