有 $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