시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB7121166418.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”를 출력한다.

예제 입력 1

4 2
1 2
2 3
4
1 2
2 3
1 3
1 4

예제 출력 1

1 2 1 gg

출처