شارك $N$ طالبًا في نهائي KOI. لنمثّلهم بالأعداد الصحيحة من $1$ إلى $N$. بعد انتهاء المسابقة، لا تعلن الإدارة ترتيب جميع الطلاب، بل تخبر أي طالبين $A,B$ يزورانها أيهما حقق نتيجة أفضل. لا يوجد طالبان أو أكثر متعادلون في النتيجة.

تشكّل الطلاب الذين يريدون معرفة ترتيبهم العام في أزواج وسألوا الإدارة ما مجموعه $M$ سؤال. عند إعطائك الطالب $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 تساوي 12 نقطة من أصل 100، وفيها $N\le10$.
• المهمة الفرعية 2 تساوي 11 نقطة من أصل 100، وفيها $N\le1,000$ و$M=N(N-1)/2$.
• المهمة الفرعية 3 تساوي 34 نقطة من أصل 100، وفيها $N\le1,000$.
• المهمة الفرعية 4 تساوي 43 نقطة من أصل 100، ولا تفرض قيودًا إضافية على القيود الأصلية.

أمثلة

الإدخال 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