수도에서의 도달 가능성

Berland에는 n개의 도시와 m개의 도로가 있다. 각 도로는 한 쌍의 도시를 연결한다. Berland의 도로는 단방향이다.

수도에서 모든 도시에 도달할 수 있도록 하기 위해 건설해야 하는 새 도로의 최소 개수는 얼마인가?

새 도로 역시 단방향이다.

입력의 첫 번째 줄에는 도시의 개수, 도로의 개수, 수도의 번호를 나타내는 세 정수 n, m, s (1 ≤ n ≤ 5000, 0 ≤ m ≤ 5000, 1 ≤ s ≤ n)이 주어진다. 도시에는 1부터 n까지 번호가 매겨져 있다.

이어지는 m개의 줄에는 도로가 주어진다. 도로 i는 한 쌍의 도시 $u_i$, $v_i$ (1 ≤ $u_i$, $v_i$ ≤ n, $u_i$ ≠ $v_i$)로 주어진다. 각 도시 쌍 (u, v)에 대해 u에서 v로 가는 도로는 최대 하나만 존재할 수 있다. 한 쌍의 도시 사이에 서로 반대 방향의 도로가 존재하는 것은 허용된다(즉, u에서 v로 가는 도로와 v에서 u로 가는 도로가 모두 존재할 수 있다).

도시 s에서 모든 도시에 도달할 수 있도록 추가해야 하는 도로의 최소 개수를 하나의 정수로 출력한다. 이미 s에서 모든 도시에 도달할 수 있다면 0을 출력한다.

첫 번째 예제는 다음 그림에 나타나 있다.

예를 들어, 도로 (6, 4), (7, 9), (1, 7)을 추가하면 s = 1에서 모든 도시에 도달할 수 있다.

두 번째 예제는 다음 그림에 나타나 있다.

이 예제에서는 도로 (5, 1), (5, 2), (5, 3), (5, 4) 중 어느 하나를 추가하면 s = 5에서 모든 도시에 도달할 수 있다.