#F4. 换乘

换乘

T4 换乘(bus)

时间限制:1.0 秒 空间限制:256 MB

题目描述

某城市有 nn 个公交站点,编号 11 到 nn,还有 mm 条公交线路。第 ii 条线路经过 kik_i 个站点(保证同一条线路内站点互不相同);线路是双向运行的,即对于一条线路上的任意两个站点,都可以乘坐该线路在它们之间往返,中途可以任意上下车。

你可以在任意站点换乘任意线路(前提是该站点在这条线路上)。从乘坐的一条线路换成另一条线路,称为一次「换乘」;在起点上车的第一条线路不计为换乘。

你目前位于站点 11,想要前往站点 nn。请你求出最少需要换乘多少次;若无论如何都无法到达站点 nn,输出 −1-1。

输入格式

第一行两个正整数 n,mn, m。

接下来 mm 行,每行先给出一个正整数 kik_i,紧接着 kik_i 个互不相同的整数,表示该线路经过的站点编号(站点编号在 11 到 nn 之间)。

输出格式

输出一个整数:最少换乘次数;若无法到达,输出 −1-1。

样例 1

输入:

6 3
3 1 3 5
3 2 3 4
2 4 6

输出:

2

样例 1 解释: 先乘线路 1 从站点 1 到站点 3,换乘线路 2 到站点 4,再换乘线路 3 到站点 6,共换乘 2 次。可以证明没有更少的方案。

样例 2

输入:

4 2
2 1 2
2 3 4

输出:

-1

样例 2 解释: 站点 {1,2}\{1, 2\} 与 {3,4}\{3, 4\} 之间没有任何线路相连,站点 4 无法到达。

样例 3

输入:

3 1
3 1 2 3

输出:

0

样例 3 解释: 站点 1 和站点 3 都在线路 1 上,直接乘坐即可,换乘 0 次。

数据范围

对于全部测试数据:2≤n≤10002 \le n \le 1000;1≤m≤5001 \le m \le 500;2≤ki≤1002 \le k_i \le 100;∑ki≤5×104\sum k_i \le 5 \times 10^4;保证同一条线路内站点互不相同。