Participaram $N$ alunos na final da KOI. Representemo-los pelos inteiros de $1$ a $N$. Depois da competição, em vez de anunciar as classificações de todos, a organização informa dois alunos $A,B$ que a procurem sobre qual deles teve melhor resultado. Não existem dois ou mais alunos empatados.

Os alunos curiosos sobre a sua classificação geral formaram pares e fizeram à organização um total de $M$ perguntas. Dados o aluno $X$ cuja classificação se pretende saber e as respostas, determine e imprima o intervalo de classificações possíveis de $X$. Naturalmente, a classificação vai de $1$, o melhor resultado geral, a $N$, o pior, mas imprima a resposta mais precisa que possa ser deduzida das respostas.

Entrada

A entrada padrão fornece as informações seguintes. A primeira linha contém três inteiros $N,M,X$ separados por espaços ($2\le N\le10^5$, $1\le M\le\min(\frac{N(N-1)}{2},5\times10^5)$, $1\le X\le N$). Cada uma das $M$ linhas seguintes contém dois inteiros $A,B$, o que significa que o aluno $A$ teve melhor resultado do que $B$. O mesmo par $A,B$ nunca aparece em mais de uma linha, e garante-se que a informação é correta.

Saída

Imprima na saída padrão dois inteiros $U,V$ ($1\le U\le V\le N$). Indicam que a melhor classificação possível do aluno $X$ é $U$ e a pior é $V$. Se $X$ tiver exatamente uma classificação possível, então $U=V$.

Subtarefas

• A subtarefa 1 vale 12 dos 100 pontos e satisfaz $N\le10$.
• A subtarefa 2 vale 11 dos 100 pontos e satisfaz $N\le1,000$, $M=N(N-1)/2$.
• A subtarefa 3 vale 34 dos 100 pontos e satisfaz $N\le1,000$.
• A subtarefa 4 vale 43 dos 100 pontos e não tem restrições além das originais.

Exemplos

Entrada 1

5 4 1
1 2
2 3
3 4
4 5

Saída 1

1 1

Entrada 2

5 3 1
2 3
3 4
4 5

Saída 2

1 5

Entrada 3

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

Saída 3

1 2