伯兰有 $$$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$$$ 可以到达所有城市。