Participaron $N$ estudiantes en la final de KOI. Representémoslos mediante los enteros del $1$ al $N$. Al terminar el concurso, en lugar de publicar las posiciones de todos, la organización informa a dos estudiantes $A,B$ que acudan a ella de cuál obtuvo mejor resultado. No hay dos o más estudiantes empatados.

Los estudiantes que querían conocer su posición global formaron parejas e hicieron un total de $M$ preguntas a la organización. Dados el estudiante $X$ cuya posición se busca y las respuestas, encuentra e imprime el intervalo de posiciones posibles de $X$. Naturalmente, su posición va de $1$, el mejor resultado global, a $N$, el peor, pero debes dar la respuesta más precisa que pueda deducirse de las respuestas.

Entrada

La entrada estándar proporciona la siguiente información. La primera línea contiene tres enteros $N,M,X$ separados por espacios ($2\le N\le10^5$, $1\le M\le\min(\frac{N(N-1)}{2},5\times10^5)$, $1\le X\le N$). Cada una de las siguientes $M$ líneas contiene dos enteros $A,B$, lo que significa que el estudiante $A$ obtuvo mejor resultado que $B$. La misma pareja $A,B$ nunca aparece en más de una línea y se garantiza que la información es correcta.

Salida

Imprime en la salida estándar dos enteros $U,V$ ($1\le U\le V\le N$). Indican que la mejor posición posible del estudiante $X$ es $U$ y la peor es $V$. Si $X$ tiene exactamente una posición posible, entonces $U=V$.

Subtareas

• La subtarea 1 vale 12 de los 100 puntos y cumple $N\le10$.
• La subtarea 2 vale 11 de los 100 puntos y cumple $N\le1,000$, $M=N(N-1)/2$.
• La subtarea 3 vale 34 de los 100 puntos y cumple $N\le1,000$.
• La subtarea 4 vale 43 de los 100 puntos y no tiene restricciones adicionales a las originales.

Ejemplos

Entrada 1

5 4 1
1 2
2 3
3 4
4 5

Salida 1

1 1

Entrada 2

5 3 1
2 3
3 4
4 5

Salida 2

1 5

Entrada 3

5 5 1
1 3
2 3
3 4
3 5
4 5

Salida 3

1 2