Problem
在N市，在不明情况下，其中一家工厂的领地变成了异常区域。该地区的所有入口都被封锁，它本身被称为工业区。工业区内有
N栋建筑，其中一些有道路相连。任何道路都可以双向行驶。
新手stalker接到的任务是去工业区的仓库。他在电子档案中找到了几张工业区版图。由于这些地图是由不同的人编制的，每张地图只包含工业区部分道路的信息。同一条道路可以出现在多张地图上。
途中，潜行者可以从存档中下载一张卡片到手机中。当您下载新地图时，之前的地图不会存储在手机内存中。潜行者只能沿着当前加载的地图上标记的道路移动。每张地图下载费用为 1 卢布。为了最小化成本，stalker 需要选择这样的路线，以便尽可能少地下载地图。 Stalker 可以多次下载同一张地图，每次下载都需要付费。最初，手机内存中没有卡。
要求编写一个程序，计算一个潜行者从工业区入口到仓库所需的最少费用。
输入：
- 输入的第一行包含两个自然数
N 和
K (
\(2 <= N <= 2000 \ );
\(1 <= K <= 2000\)) —分别是工业区建筑物的数量和地图的数量。工业区入口位于编号为
1的大楼内，仓库——在
N 楼。
- 在以下几行中有关于可用卡的信息。第
i 张卡的描述的第一行包含数字
ri —第
i 张地图上标记的道路数量；
- 然后
ri 字符串包含两个自然数
a 和
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\))，意思是在第
i 个地图上有一条路连接建筑物
a 和
b< /代码>。所有地图上标记的道路总数不超过 300,000 (\(r_1 + r_2 + … + r_K <= 300,000\))。
输出： 打印一个数字 —缠扰者的最低开支。如果无法到达仓库，请打印数字 –1。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
12 4
4
16
24
第79话
10 12
3
14
7 11
36
3
25
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |