分数: 400 分
问题陈述
高桥生活在一个城市 N 公交车站。巴士站编号为 1 to N.
有 M 在本市运营的公交线路,编号从 1 to M.
巴士路线 i 穿过 K_i 巴士站 A_{i,1}, A_{i,2}, \dots, A_{i,K_i}.
乘坐此路线,您可以在其中任一巴士站上车并在其中任一其他巴士站下车。
高桥最初在公交车站 S 想去公交车站 T.
Takahashi 可以重复以下操作任意次数(包括零次):
- 选择一条经过他当前所在公交车站的公交路线并搭乘。然后在该路线经过的任何一个公交车站(与当前车站不同)下车。
同一条巴士路线可以多次使用。
求到达公交车站所需的最少操作次数(即最少乘车次数) T。如果无法到达,则输出 -1.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^5
- 1 \leq S \leq N
- 1 \leq T \leq N
- 1 \leq K_i \leq N (1 \leq i \leq M)
- 1 \leq A_{i,j} \leq N (1 \leq i \leq M,\ 1 \leq j \leq K_i)
- 对于每个 i, A_{i,1}, A_{i,2}, \dots, A_{i,K_i} 都是不同的。
- \displaystyle \sum_{i=1}^{M} K_i \leq 5 \times 10^5
- 所有输入值均为整数。
输入
N M S T
K_1 A_{1,1} A_{1,2} \dots A_{1,K_1}
K_2 A_{2,1} A_{2,2} \dots A_{2,K_2}
\vdots
K_M A_{M,1} A_{M,2} \dots A_{M,K_M}
- 第一行包含公交车站数量 N, 公交线路数量 M, 起始公交车站号 S,以及目的地巴士站号码 T,用空格分隔。
- 的 i- 以下各项 M 线路包含巴士路线信息 i.
- 主导价值 K_i 代表该巴士路线的巴士站数量 i 穿过。
- 以下 K_i 整数 A_{i,1}, A_{i,2}, \dots, A_{i,K_i} 代表巴士路线的巴士站号码 i 穿过。
输出
在一行中输出到达公交车站所需的最少乘车次数 T。如果无法到达,则输出 -1.
样本输入 1
5 3 1 5 3 1 2 3 2 3 4 2 2 5
示例输出 1
2
示例输入 2
6 3 1 6 2 1 2 2 2 3 2 5 6
示例输出 2
-1
示例输入 3
12 7 1 12 4 1 2 3 4 3 4 5 6 3 6 7 8 3 2 9 10 2 10 12 3 8 11 12 3 3 7 9
示例输出 3
3
示例输入 4
20 10 1 20 5 1 2 3 4 5 4 5 6 7 8 4 8 9 10 11 4 11 12 13 14 4 14 15 16 20 3 3 9 15 4 2 6 12 18 3 18 19 20 2 7 17 3 10 17 20
示例输出 4
3
示例输入 5
1 1 1 1 1 1
示例输出 5
0