C - Spread of Rumors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

N 人の人々がおり、それぞれ 1 から N までの番号が付けられています。人々の間には全部で M 本の一方向の連絡手段があり、i 番目の連絡手段では人 U_i から人 V_i へメッセージを送ることができます。

はじめ（日 0 の開始時点）では、人 S だけがあるうわさを知っています。うわさの伝播は次のルールに従って日ごとに進みます。

  • 日 d（d = 0, 1, 2, \ldots）の開始時点でうわさを知っている各人は、その人を送信元とするすべての連絡手段を通じて、うわさを一斉に送ります。送られたうわさは日 d+1 の開始時点で届き、届いた人はその時点からうわさを知っている状態になります。
  • 日 d+1 の開始時点で新たにうわさを知った人が実際にうわさを送れるのは、日 d+1 以降です。
  • 一度うわさを知った人は、以降ずっとうわさを知っている状態のままです。

すべての人がうわさを知っている状態に最初になる日 d を求めてください。すなわち、日 d の開始時点ではじめてすべての人がうわさを知っている状態であるような最小の d を出力してください。日 0 の開始時点ですでにすべての人がうわさを知っている場合（N = 1 の場合など）は 0 を出力してください。どれだけ日数が経ってもすべての人にうわさが広まらない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 4 \times 10^5
  • 0 \leq M < 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i（自己ループは存在しない）
  • 同じ順序対 (U_i, V_i) は高々 1 つしか存在しない
  • 入力はすべて整数である

入力

N M S
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、人数を表す N、連絡手段の数を表す M、最初にうわさを知っている人の番号を表す S が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目には、連絡手段の情報が与えられる。
  • 1 + i 行目では、i 番目の連絡手段が人 U_i から人 V_i へ向かうことを表す U_i、V_i が、スペース区切りで与えられる。

出力

すべての人がうわさを知っている状態になる最も早い日 d を 1 行で出力せよ。ただし、すべての人にうわさが広まらない場合は -1 を出力せよ。

入力例 1

4 4 1
1 2
1 3
2 4
3 4

出力例 1

2

入力例 2

5 4 2
2 3
3 4
4 2
1 5

出力例 2

-1

入力例 3

8 10 5
5 1
5 2
1 3
2 3
2 6
3 4
6 7
4 8
7 8
6 2

出力例 3

4

入力例 4

15 22 10
10 1
10 2
10 3
1 4
1 5
2 5
2 6
3 6
3 7
4 8
5 8
5 9
6 9
6 11
7 11
8 12
8 9
9 13
11 14
12 15
13 15
14 15

出力例 4

5

入力例 5

1 0 1

出力例 5

0

Score : 366 pts

Problem Statement

There are N people, numbered from 1 to N. There are a total of M one-way communication channels among the people. The i-th communication channel allows person U_i to send a message to person V_i.

Initially (at the start of day 0), only person S knows a certain rumor. The spread of the rumor proceeds day by day according to the following rules:

  • Each person who knows the rumor at the start of day d (d = 0, 1, 2, \ldots) simultaneously sends the rumor through all communication channels originating from that person. The sent rumors arrive at the start of day d+1, and the recipients become aware of the rumor from that point onward.
  • A person who newly learns the rumor at the start of day d+1 can only actually send the rumor from day d+1 onward.
  • Once a person learns the rumor, they remain aware of it permanently.

Find the day d when all people first become aware of the rumor. That is, output the smallest d such that at the start of day d, all people know the rumor for the first time. If all people already know the rumor at the start of day 0 (such as when N = 1), output 0. If the rumor cannot reach all people no matter how many days pass, output -1.

Constraints

  • 1 \leq N \leq 4 \times 10^5
  • 0 \leq M < 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i (no self-loops exist)
  • Each ordered pair (U_i, V_i) appears at most once
  • All input values are integers

Input

N M S
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains N representing the number of people, M representing the number of communication channels, and S representing the number of the person who initially knows the rumor, separated by spaces.
  • Lines 2 through M + 1 contain the communication channel information.
  • The (1 + i)-th line contains U_i and V_i, separated by spaces, indicating that the i-th communication channel goes from person U_i to person V_i.

Output

Output in a single line the earliest day d when all people become aware of the rumor. However, if the rumor cannot spread to all people, output -1.

Sample Input 1

4 4 1
1 2
1 3
2 4
3 4

Sample Output 1

2

Sample Input 2

5 4 2
2 3
3 4
4 2
1 5

Sample Output 2

-1

Sample Input 3

8 10 5
5 1
5 2
1 3
2 3
2 6
3 4
6 7
4 8
7 8
6 2

Sample Output 3

4

Sample Input 4

15 22 10
10 1
10 2
10 3
1 4
1 5
2 5
2 6
3 6
3 7
4 8
5 8
5 9
6 9
6 11
7 11
8 12
8 9
9 13
11 14
12 15
13 15
14 15

Sample Output 4

5

Sample Input 5

1 0 1

Sample Output 5

0