题目描述

33DAI 要从 $1$ 号公交站坐车到 $n$ 号公交站。城市里一共有 $n$ 个站点、$m$ 条公交线路。

第 $i$ 条线路会停靠 $k_i$ 个站点（这些站点互不相同）。只要坐上这条线路，就可以在它的任意两个停靠站之间直达，中途不需要换乘。坐一条线路记作乘车 $1$ 次。

33DAI 想知道：从 $1$ 号站到 $n$ 号站，最少需要坐几次车？如果到不了，输出 $-1$。

特别地，如果 $1$ 号站就是 $n$ 号站（即 $n = 1$），他不需要坐车，答案是 $0$。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $m$ 行，第 $i$ 行先是一个整数 $k_i$，接着是 $k_i$ 个整数，表示第 $i$ 条线路停靠的站点编号。同一行的 $k_i$ 个站点互不相同，相邻两个整数之间用一个空格隔开。

输出格式

输出一行一个整数，表示最少乘车次数；如果无法到达，输出 -1。

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

3

样例 1 解释

一种乘车方案是：

• 坐第 $1$ 条线路，从 $1$ 号站到 $3$ 号站；
• 换乘第 $2$ 条线路，从 $3$ 号站到 $4$ 号站；
• 换乘第 $3$ 条线路，从 $4$ 号站到 $6$ 号站。

一共坐了 $3$ 条线路，所以答案是 3。

5 2
2 1 2
2 3 4

-1

样例 2 解释

第 $1$ 条线路只经过 $1, 2$ 号站，第 $2$ 条线路只经过 $3, 4$ 号站，两组站点之间没有任何线路相连。$5$ 号站没有任何线路经过，从 $1$ 号站无法到达 $n = 5$ 号站，输出 -1。

样例 3

见 bus3.in 与 bus3.ans。

样例 4

见 bus4.in 与 bus4.ans。

数据范围

对于全部测试数据，保证：

• $1 \le n \le 2 \times 10^5$；
• $0 \le m \le 2 \times 10^5$；
• 每条线路的停靠站数 $k_i \ge 2$，且同一条线路内的站点互不相同；
• 所有线路的停靠站数之和 $\sum k_i \le 2 \times 10^5$；
• 所有站点编号都在 $1$ 到 $n$ 之间。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。