← 返回题目列表

AtCoder · awc0081_c

C. 谣言的传播

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

分数: 366 分

问题陈述

有 N 人,编号自 1 to 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) 最多出现一次
  • 所有输入值均为整数

输入

N M S
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 第一行包含 N 代表人数, M 代表通信通道的数量,以及 S 代表最初知道该谣言的人数,以空格分隔。
  • 线 2 通过 M + 1 包含通信通道信息。
  • 的 (1 + i)第行包含 U_i 和 V_i,以空格分隔,表示 i第一个沟通渠道来自人 U_i 对人 V_i.

输出

最早一天以单行输出 d 当所有人都知道谣言时。然而,如果谣言无法传播到所有人,则输出 -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