W finale KOI wzięło udział $N$ uczniów. Oznaczmy ich liczbami całkowitymi od $1$ do $N$. Po zawodach, zamiast ogłaszać miejsca wszystkich uczniów, organizatorzy informują dwóch uczniów $A,B$, którzy się do nich zgłoszą, który z nich uzyskał lepszy wynik. Żadnych dwóch ani więcej uczniów nie ma takiego samego wyniku.

Uczniowie ciekawi swoich miejsc w klasyfikacji dobierali się w pary i zadali organizatorom łącznie $M$ pytań. Mając danego ucznia $X$ oraz odpowiedzi organizatorów, znajdź i wypisz zakres możliwych miejsc ucznia $X$. Oczywiście miejsce leży od $1$, oznaczającego najlepszy wynik, do $N$, oznaczającego najgorszy wynik, lecz należy podać najdokładniejszą odpowiedź wynikającą z uzyskanych informacji.

Wejście

Na standardowym wejściu podano następujące informacje. Pierwszy wiersz zawiera trzy liczby całkowite $N,M,X$ oddzielone spacjami ($2\le N\le10^5$, $1\le M\le\min(\frac{N(N-1)}{2},5\times10^5)$, $1\le X\le N$). Każdy z kolejnych $M$ wierszy zawiera dwie liczby całkowite $A,B$, co oznacza, że uczeń $A$ uzyskał lepszy wynik niż uczeń $B$. Ta sama para $A,B$ nie występuje w więcej niż jednym wierszu, a poprawność informacji jest zagwarantowana.

Wyjście

Wypisz na standardowe wyjście dwie liczby całkowite $U,V$ ($1\le U\le V\le N$). Oznaczają one, że najlepsze możliwe miejsce ucznia $X$ to $U$, a najgorsze to $V$. Jeśli uczeń $X$ ma dokładnie jedno możliwe miejsce, zachodzi $U=V$.

Podzadania

• Podzadanie 1 jest warte 12 ze 100 punktów i spełnia $N\le10$.
• Podzadanie 2 jest warte 11 ze 100 punktów i spełnia $N\le1,000$, $M=N(N-1)/2$.
• Podzadanie 3 jest warte 34 ze 100 punktów i spełnia $N\le1,000$.
• Podzadanie 4 jest warte 43 ze 100 punktów i nie ma ograniczeń poza pierwotnymi.

Przykład

Wejście 1

5 4 1
1 2
2 3
3 4
4 5

Wyjście 1

1 1

Wejście 2

5 3 1
2 3
3 4
4 5

Wyjście 2

1 5

Wejście 3

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

Wyjście 3

1 2