← 返回题目列表

Codeforces · 999/E

E. 从首都出发的可达性

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

伯兰有 $$$n$$$ 个城市和 $$$m$$$ 道路。每条道路连接一对城市。贝尔兰的道路是单向的。

至少需要修建多少条新道路才能从首都到达所有城市?

新道路也将是单向的。

输入

输入的第一行由三个整数 $$$n$$$、$$$m$$$ 和 $$$s$$$ ($$$1 \le n \le 5000, 0 \le m \le 5000, 1 \le s \le n$$$) 组成 - 城市数量、道路数量和首都索引。城市索引从 $$$1$$$ 到 $$$n$$$。

以下 $$$m$$$ 行包含道路:道路 $$$i$$$ 被指定为一对城市 $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$)。对于每对城市 $$$(u, v)$$$,最多可以有一条从 $$$u$$$ 到 $$$v$$$ 的道路。两个城市之间允许有相反方向的道路(即从 $$$u$$$ 到 $$$v$$$ 以及从 $$$v$$$ 到 $$$u$$$)。

输出

打印一个整数 — 从城市 $$$s$$$ 到达所有城市所需的最少额外道路数量。如果从 $$$s$$$ 可以到达所有城市,则打印 0。

示例

输入 #1

9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1

输出 #1

3

输入 #2

5 4 5
1 2
2 3
3 4
4 1

输出 #2

1

注意

第一个示例如下所示:

例如,您可以添加道路 ($$$6, 4$$$)、($$$7, 9$$$)、($$$1, 7$$$) 以使从 $$$s = 1$$$ 可以到达所有城市。

第二个示例如下所示:

在此示例中,您可以添加任意一条道路 ($$$5, 1$$$)、($$$5, 2$$$)、($$$5, 3$$$)、($$$5, 4$$$) 以使从 $$$s = 5$$$ 可以到达所有城市。