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