← 返回题目列表

AtCoder · awc0061_d

D. 巴士路线换乘

中文机器翻译题面 查看原题

分数: 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