페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3428

등수 찾기(ranking) 2초 1024MB

문제

KOI 본선 대회에 N명의 학생이 참가했다. 이 학생들을 각각 1부터 N​까지 정수로 표현하자. 

대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표하는 대신, 

두 학생 A, B가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 

둘 이상의 학생이 동점인 경우는 없다.

 

자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 M번 질문을 했다. 

여러분은 등수를 알고 싶은 학생 X와 대회 본부의 질문에 대한 답들로부터, 

이 학생 X의 등수 범위를 찾아서 출력한다. 

물론 이 학생의 등수는 1등, 즉 전체에서 제일 잘한 경우부터 

N등, 즉 전체에서 제일 못한 경우 사이겠지만, 질문에 대한 답으로 알 수 있는 최대한 정확한 답을 출력한다.


입력

첫 번째 줄에 세 정수 N, M, X 가 공백을 사이에 두고 주어진다

( 2 ≤ N ≤ 10^5, 1 ≤ M ≤ min(N(N-1)/2, 5×10^5 ), 1 ≤ X ≤ N).

다음 M 줄에는 각각 두 정수 A, B가 주어지는데, 

이 뜻은 학생 A가 학생 B보다 더 잘했다는 뜻이다. 

같은 A, B가 둘 이상의 줄에 주어지는 경우는 없고, 

입력된 값이 정확함이 보장된다.


출력

두 정수 U, V ( 1 ≤ U ≤ V ≤ N) 를 출력한다.

이는 학생 X의 가능한 가장 높은 등수가 U, 가능한 가장 낮은 등수가 V임을 나타낸다. 

만약 학생 X의 가능한 등수가 정확하게 하나라면, U = V이다. 


부분문제

번호 점수 조건
#112점

N ≤ 10

#211점

N ≤ 1,000, M = N(N-1)/2

#334점

N ≤ 1,000

#443점

추가 제약조건이 없다.


예제1

입력
541

12

23

34

45
출력
11

예제2

입력
531

23

34

45
출력
15

예제3

입력
551

13

23

34

35

45
출력
12

출처

KOI 2차 2019 초3

역링크