Am KOI-Finale nahmen $N$ Schüler teil. Wir bezeichnen sie mit den ganzen Zahlen von $1$ bis $N$. Nach dem Wettbewerb veröffentlicht die Wettbewerbsleitung nicht alle Ränge, sondern teilt zwei Schülern $A,B$, die zu ihr kommen, mit, wer von ihnen besser abgeschnitten hat. Es gibt keine zwei oder mehr Schüler mit gleichem Ergebnis.

Schüler, die ihren Gesamtrang wissen wollten, bildeten Paare und stellten der Wettbewerbsleitung insgesamt $M$ Fragen. Bestimme und gib anhand des gesuchten Schülers $X$ und der Antworten den Bereich seiner möglichen Ränge aus. Natürlich liegt sein Rang zwischen $1$, dem besten Gesamtergebnis, und $N$, dem schlechtesten, aber gib die genaueste aus den Antworten ableitbare Antwort aus.

Eingabe

Die Standardeingabe enthält folgende Informationen. Die erste Zeile enthält drei durch Leerzeichen getrennte ganze Zahlen $N,M,X$ ($2\le N\le10^5$, $1\le M\le\min(\frac{N(N-1)}{2},5\times10^5)$, $1\le X\le N$). Jede der nächsten $M$ Zeilen enthält zwei ganze Zahlen $A,B$ und besagt, dass Schüler $A$ besser als Schüler $B$ abgeschnitten hat. Dasselbe Paar $A,B$ steht nie in mehreren Zeilen, und die Angaben sind garantiert korrekt.

Ausgabe

Gib zwei ganze Zahlen $U,V$ ($1\le U\le V\le N$) auf der Standardausgabe aus. Sie bedeuten, dass der bestmögliche Rang von Schüler $X$ gleich $U$ und der schlechtestmögliche gleich $V$ ist. Ist genau ein Rang für $X$ möglich, gilt $U=V$.

Teilaufgaben

• Teilaufgabe 1 ist 12 von insgesamt 100 Punkten wert und erfüllt $N\le10$.
• Teilaufgabe 2 ist 11 von insgesamt 100 Punkten wert und erfüllt $N\le1,000$, $M=N(N-1)/2$.
• Teilaufgabe 3 ist 34 von insgesamt 100 Punkten wert und erfüllt $N\le1,000$.
• Teilaufgabe 4 ist 43 von insgesamt 100 Punkten wert und hat keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

5 4 1
1 2
2 3
3 4
4 5

Ausgabe 1

1 1

Eingabe 2

5 3 1
2 3
3 4
4 5

Ausgabe 2

1 5

Eingabe 3

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

Ausgabe 3

1 2