有 $N$ 名學生參加了 KOI 決賽，用從 $1$ 到 $N$ 的整數分別表示他們。比賽結束後公布成績時，主辦方並不公布所有學生的排名，而是在兩名學生 $A,B$ 前來詢問時，告訴他們哪一名表現更好。不存在兩名或更多學生同分的情況。

想知道自己總排名的學生兩兩結對，共向主辦方詢問了 $M$ 次。給定想知道排名的學生 $X$ 以及主辦方的回答，求出並輸出 $X$ 的可能排名範圍。當然，他的排名介於第 $1$ 名（全體中表現最好）和第 $N$ 名（全體中表現最差）之間，但需要輸出從這些回答中能夠得知的最精確結果。

輸入格式

標準輸入給出如下資訊。第一行包含三個用空格分隔的整數 $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$）。接下來 $M$ 行每行包含兩個整數 $A,B$，表示學生 $A$ 的表現比學生 $B$ 好。同一對 $A,B$ 不會出現在多行中，保證輸入資訊正確。

輸出格式

向標準輸出輸出兩個整數 $U,V$（$1\le U\le V\le N$），表示學生 $X$ 可能的最好排名為 $U$，可能的最差排名為 $V$。如果學生 $X$ 只有一種可能的排名，則 $U=V$。

子任務

• 子任務 1：占總分 100 分中的 12 分，滿足 $N\le10$。
• 子任務 2：占總分 100 分中的 11 分，滿足 $N\le1,000$，$M=N(N-1)/2$。
• 子任務 3：占總分 100 分中的 34 分，滿足 $N\le1,000$。
• 子任務 4：占總分 100 分中的 43 分，除原有限制外無其他限制。

範例

輸入格式 1

5 4 1
1 2
2 3
3 4
4 5

輸出格式 1

1 1

輸入格式 2

5 3 1
2 3
3 4
4 5

輸出格式 2

1 5

輸入格式 3

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

輸出格式 3

1 2