$N$ élèves ont participé à la finale de KOI. Représentons-les par les entiers de $1$ à $N$. Après le concours, au lieu de publier les rangs de tous les élèves, les organisateurs indiquent à deux élèves $A,B$ qui viennent les voir lequel a obtenu le meilleur résultat. Il n'y a jamais deux élèves ou plus à égalité.

Les élèves curieux de leur rang général se sont mis par deux et ont posé au total $M$ questions aux organisateurs. Étant donnés l'élève $X$ dont on cherche le rang et les réponses, trouvez et affichez l'intervalle des rangs possibles de $X$. Son rang est naturellement compris entre $1$, le meilleur résultat général, et $N$, le pire, mais affichez la réponse la plus précise que les réponses permettent de déduire.

Entrée

L'entrée standard fournit les informations suivantes. La première ligne contient trois entiers $N,M,X$ séparés par des espaces ($2\le N\le10^5$, $1\le M\le\min(\frac{N(N-1)}{2},5\times10^5)$, $1\le X\le N$). Chacune des $M$ lignes suivantes contient deux entiers $A,B$, signifiant que l'élève $A$ a obtenu un meilleur résultat que $B$. La même paire $A,B$ ne figure jamais sur plusieurs lignes, et les informations sont garanties correctes.

Sortie

Affichez sur la sortie standard deux entiers $U,V$ ($1\le U\le V\le N$). Ils indiquent que le meilleur rang possible de l'élève $X$ est $U$ et que le pire est $V$. Si $X$ n'a qu'un seul rang possible, alors $U=V$.

Sous-tâches

• La sous-tâche 1 vaut 12 points sur 100 et vérifie $N\le10$.
• La sous-tâche 2 vaut 11 points sur 100 et vérifie $N\le1,000$, $M=N(N-1)/2$.
• La sous-tâche 3 vaut 34 points sur 100 et vérifie $N\le1,000$.
• La sous-tâche 4 vaut 43 points sur 100 et n'impose aucune contrainte supplémentaire.

Exemples

Entrée 1

5 4 1
1 2
2 3
3 4
4 5

Sortie 1

1 1

Entrée 2

5 3 1
2 3
3 4
4 5

Sortie 2

1 5

Entrée 3

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

Sortie 3

1 2