KOI 본선 대회에 \(N\)명의 학생이 참가했다. 이 학생들을 각각 \(1\)부터 \(N\)까지 정수로 표현하자. 대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표하는 대신, 두 학생 \(A\), \(B\)가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 두 이상의 학생이 동점인 경우는 없다.

자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 \(M\)번 질문을 했다. 여러분은 등수를 알고 싶은 학생 \(X\)와 대회 본부의 질문에 대한 답으로부터, 이 학생 \(X\)의 등수 범위를 찾아서 출력해야 한다. 물론 이 학생의 등수는 \(1\)등, 즉 전체에서 제일 잘한 경우부터 \(N\)등, 즉 전체에서 제일 못한 경우 사이겠지만, 질문에 대한 답으로 알 수 있는 최대한 정확한 답을 출력해야 한다.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다.

첫 번째 줄에 세 정수 \(N\), \(M\), \(X\)가 공백을 사이에 두고 주어진다. (\(2 \le N \le 10^5\), \(1 \le M \le \min\left(\dfrac{N(N-1)}{2},\, 5 \times 10^5\right)\), \(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\)이다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2019 > 2차 대회 > 초등부 3번