En el vasto mundo de Azeroth, existen varios continentes, para moverse entre ellos es necesario usar barcos. Estos tienen una ruta en una dirección específica. La Alianza está teniendo problemas para planear las rutas desde la capital(Ventormenta), así que los ingenieros gnomos te han pedido crear un programa que resuelva el siguiente problema.

Dadas ~n~ ciudades, enumeradas de ~1~ a ~n~ y ~m~ rutas iniciales. ¿Cuál es la mínima cantidad de rutas que se necesita agregar a la planificación para poder llegar desde un barco que sale de la capital(Ventormenta) a cualquier otra ciudad?

Nota: recuerde que las rutas son dirigidas(en un solo sentido), es decir la ruta ~u \rightarrow v~ lleva desde la ciudad ~u~ hasta ~v~

Entrada:

La primera línea contiene tres enteros ~n~, ~m~ y ~s~ (~2 \leq n \leq 10^{5}, 1 \leq m \leq 10^{5}, 1 \leq s \leq n~). El número de ciudades, el número de rutas iniciales y el número que representa a la capital(Ventormenta) respectivamente.

Las siguientes ~m~ líneas contienen las rutas iniciales. La ruta ~i~ es dada como un par de ciudades ~u_{i}~, ~v_{i}~ (~1\leq u_{i}, v_{i} \leq n~, ~u_{i} \neq v_{i}~). Para cada par de ciudades (~u,v~) habrá a lo más una ruta directa de ~u~ a ~v~. Las rutas en la dirección opuesta entre un par de ciudades están permitidas (de ~u~ a ~v~ y de ~v~ a ~u~).

Salida:

Imprime un entero. El mínimo número de rutas adicionales que tienes que añadir para poder visitar cualquier ciudad si el barco sale desde la capital(Ventormenta). Si todas las ciudades ya son alcanzables, imprime ~0~.

Subtareas:

-Subtarea 1: ~n \leq 20~ (15 puntos).
-Subtarea 2: Para cada arista ~u_{i} \rightarrow v_{i}~ en la entrada se garantiza ~u_{i} < v_{i}~ y ~n \leq 5000~ (20 puntos).
-Subtarea 3: ~1 \leq n, m \leq 5000~ (40 puntos).
-Subtarea 4: Sin restricciones adicionales (25 puntos).

Ejemplos

Entrada 1

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

Salida 1

3

Entrada 2

5 4 5  
1 2  
2 3  
3 4  
4 1

Salida 2

1

Entrada 3

3 2 2  
1 2  
3 2

Salida 3

2

Explicacion de los casos de ejemplo:

En el siguiente grafo está representado el ejemplo 1.

Podemos añadir las rutas (6,4), (7,9), (1,7) para hacer todas las ciudades alcanzables desde s=1.

Para el segundo ejemplo:

Podemos añadir alguna de las rutas (5,1), (5,2), (5,3), (5,4) para hacer todas las ciudades alcanzables desde s=5.

Para el tercer ejemplo:

Añadir las rutas (2,1) y (2,3) es una posible solución.