시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 712 | 116 | 64 | 18.551% |
모두에게 속여왔지만 사실 김지민은 한국의 최고령이다.
지민이는 자신이 나이가 가장 많다는 사실을 알고있지만, 다른 사람들의 나이는 몇 살인지 알지 못한다.
하지만 지민이에게는 최고령자로써의 특별한 능력이 있어서 어떤 두 사람을 보면 누가 더 나이가 많은지 알 수 있다.
이 사기적인 능력을 언제나 사용하면 좋겠지만, 지민이가 너무 늙은 나머지 여러 번 사용하면 힘에 부치기 때문에 m번만 사용하려고 한다.
n명의 사람들이 있다. 지민이는 이 사람들 중에서 두 명을 뽑아 나이를 비교하는 것을 m번 할 수 있다.
그 이후, 어떤 두 사람사이의 나이 관게를 파악하고자 한다. 만약 민식이보다 유진이가 나이가 높고 유진이보다 지민이가 나이가 높다면 민식이보다 지민이가 나이가 높다는 것을 알 수 있을것이다.
우리는 위와 같은 방법을 이용해서, 두 사람의 나이를 비교하고 싶다.
첫째 줄에는 사람들의 수N(<=1,000,000)과 지민이의 사기적인 능력의 사용횟수 M(<=1,000,000)이 주어진다. 두 번째 줄부터 M+1번째 줄 까지는 a b의 형태로 a와 b의 나이를 비교했을 때 a가 더 늙었다 라는 의미가 주어진다. 이름의 길이는 6byte이하이다.
M+2번째 줄에는 궁금한 쿼리의 개수 Q(<=20)가 주어진다. M+3번째 줄에서 M+Q+2번째 줄 까지는 a b의 형태로 a와 b의 나이를 비교했을 때 누가 더 나이가 많은지 알고싶다는 의미이다.
Q개의 숫자로 각각 쿼리마다 나이가 더 많은 사람의 이름을 출력한다. 나이가 같거나 알 수 없다면 “gg”를 출력한다.
4 2 1 2 2 3 4 1 2 2 3 1 3 1 4
1 2 1 gg