KOI の本選に $N$ 人の生徒が参加しました。それぞれを $1$ から $N$ までの整数で表します。大会終了後の成績発表では全員の順位を発表せず、2人の生徒 $A,B$ が大会本部を訪れると、どちらの成績がよかったかを教えます。2人以上が同点になることはありません。

全体での順位を知りたい生徒たちは2人ずつ組み、本部に合計 $M$ 回質問しました。順位を知りたい生徒 $X$ と本部の回答が与えられるので、$X$ の可能な順位の範囲を求めて出力してください。当然、順位は全体で最もよい $1$ 位から最も悪い $N$ 位までですが、回答から分かる最も正確な結果を出力してください。

入力

標準入力から次の情報を与えます。1行目に空白区切りの3整数 $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$ 行に2整数 $A,B$ を与え、生徒 $A$ の成績が生徒 $B$ よりよかったことを表します。同じ組 $A,B$ が複数の行に現れることはなく、入力情報は正しいことが保証されます。

出力

標準出力に2整数 $U,V$（$1\le U\le V\le N$）を出力してください。これは、生徒 $X$ の可能な最上位が $U$、可能な最下位が $V$ であることを表します。生徒 $X$ の可能な順位がちょうど1つなら $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