$N$ students took part in the KOI final round. Represent them by the integers from $1$ to $N$. After the contest, instead of announcing every student's rank, the contest headquarters tells any two students $A,B$ who visit which of them did better. No two or more students have tied scores.

Students curious about their overall ranks formed pairs and asked the headquarters a total of $M$ questions. Given the student $X$ whose rank is sought and the headquarters' answers, find and print the range of possible ranks of $X$. Naturally the rank is between $1$, meaning best overall, and $N$, meaning worst overall, but print the most precise answer that can be deduced from the answers.

Input

The following information is given on standard input. The first line contains three space-separated integers $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$). Each of the next $M$ lines contains two integers $A,B$, meaning that student $A$ did better than student $B$. The same pair $A,B$ is never given on more than one line, and the information is guaranteed to be correct.

Output

Print two integers $U,V$ ($1\le U\le V\le N$) to standard output. They mean that the best possible rank of student $X$ is $U$ and the worst possible rank is $V$. If student $X$ has exactly one possible rank, then $U=V$.

Subtasks

• Subtask 1 is worth 12 of the total 100 points and has $N\le10$.
• Subtask 2 is worth 11 of the total 100 points and has $N\le1,000$, $M=N(N-1)/2$.
• Subtask 3 is worth 34 of the total 100 points and has $N\le1,000$.
• Subtask 4 is worth 43 of the total 100 points and has no constraints beyond the original ones.

Examples

Input 1

5 4 1
1 2
2 3
3 4
4 5

Output 1

1 1

Input 2

5 3 1
2 3
3 4
4 5

Output 2

1 5

Input 3

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

Output 3

1 2