CF999E.Reachability from the Capital

There are $n$ cities and $m$ roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.

What is the minimum number of new roads that need to be built to make all the cities reachable from the capital?

New roads will also be one-way.

Berland 有 $n$ 座城市和 $m$ 条道路。每条道路连接一对城市。Berland 的道路均为单向道路。

为使所有城市均可从首都到达，至少需要新建多少条道路？

新建的道路也均为单向道路。

The first line of input consists of three integers $n$, $m$ and $s$ ($1 \le n \le 5000, 0 \le m \le 5000, 1 \le s \le n$) — the number of cities, the number of roads and the index of the capital. Cities are indexed from $1$ to $n$.

The following $m$ lines contain roads: road $i$ is given as a pair of cities $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). For each pair of cities $(u, v)$, there can be at most one road from $u$ to $v$. Roads in opposite directions between a pair of cities are allowed (i.e. from $u$ to $v$ and from $v$ to $u$).

输入的第一行包含三个整数 $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$ 的道路）。

Print one integer — the minimum number of extra roads needed to make all the cities reachable from city $s$. If all the cities are already reachable from $s$, print 0.

输出一个整数——使所有城市均可从城市 $s$ 到达所需的最少新增道路数量。如果所有城市已均可从 $s$ 到达，则输出 0。

The first example is illustrated by the following:

For example, you can add roads ($6, 4$), ($7, 9$), ($1, 7$) to make all the cities reachable from $s = 1$.

The second example is illustrated by the following:

In this example, you can add any one of the roads ($5, 1$), ($5, 2$), ($5, 3$), ($5, 4$) to make all the cities reachable from $s = 5$.

第一个示例图示如下：

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

第二个示例图示如下：

在此示例中，你只需添加以下任意一条道路：$(5, 1)$、$(5, 2)$、$(5, 3)$ 或 $(5, 4)$，即可使所有城市均可从起点 $s = 5$ 到达。