D - Bus Route Transfers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、N 個のバス停がある街に住んでいる。バス停には 1 から N の番号がついている。

この街には M 本のバス路線が運行されており、バス路線には 1 から M の番号がついている。

バス路線 i は K_i 個のバス停 A_{i,1}, A_{i,2}, \dots, A_{i,K_i} を通る。

この路線に乗ると、これらのバス停のうち任意の 1 つから乗車し、任意の別の 1 つで下車することができる。

高橋君は最初バス停 S にいて、バス停 T に行きたい。

高橋君は次の操作を 0 回以上好きなだけ繰り返せる。

  • 現在いるバス停を通るバス路線を 1 つ選んで乗車する。その路線が通るバス停のうち、現在いるバス停とは異なる好きなバス停で下車する。

同じバス路線を複数回利用してもよい。

バス停 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}
  • 1 行目には、バス停の個数 N、バス路線の本数 M、出発地のバス停番号 S、目的地のバス停番号 T が、スペース区切りで与えられる。
  • 続く M 行のうち i 番目の行には、バス路線 i の情報が与えられる。
  • 先頭の K_i は、バス路線 i が通るバス停の個数を表す。
  • 続く K_i 個の整数 A_{i,1}, A_{i,2}, \dots, A_{i,K_i} は、バス路線 i が通るバス停の番号を表す。

出力

バス停 T に到達するために必要な最小の乗車回数を 1 行で出力せよ。到達できない場合は -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

Score : 400 pts

Problem Statement

Takahashi lives in a city with N bus stops. The bus stops are numbered from 1 to N.

There are M bus routes operating in this city, numbered from 1 to M.

Bus route i passes through K_i bus stops A_{i,1}, A_{i,2}, \dots, A_{i,K_i}.

By taking this route, one can board at any one of these bus stops and get off at any other one of these bus stops.

Takahashi is initially at bus stop S and wants to go to bus stop T.

Takahashi can repeat the following operation any number of times (including zero):

  • Choose a bus route that passes through the bus stop he is currently at and board it. Then get off at any bus stop (different from the current one) that the route passes through.

The same bus route may be used multiple times.

Find the minimum number of operations (i.e., the minimum number of rides) required to reach bus stop T. If it is impossible to reach it, output -1.

Constraints

  • 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）
  • For each i, A_{i,1}, A_{i,2}, \dots, A_{i,K_i} are all distinct.
  • \displaystyle \sum_{i=1}^{M} K_i \leq 5 \times 10^5
  • All input values are integers.

Input

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}
  • The first line contains the number of bus stops N, the number of bus routes M, the starting bus stop number S, and the destination bus stop number T, separated by spaces.
  • The i-th of the following M lines contains the information for bus route i.
  • The leading value K_i represents the number of bus stops that bus route i passes through.
  • The following K_i integers A_{i,1}, A_{i,2}, \dots, A_{i,K_i} represent the bus stop numbers that bus route i passes through.

Output

Output in one line the minimum number of rides required to reach bus stop T. If it is impossible to reach it, output -1.

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

-1

Sample Input 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

Sample Output 3

3

Sample Input 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

Sample Output 4

3

Sample Input 5

1 1 1 1
1 1

Sample Output 5

0