나이 관계

지민이는 두 사람을 보면 어느 쪽이 더 나이가 많은지 알 수 있는 특별한 능력이 있다. 이 능력으로 M개의 비교 결과를 얻었다.

각 비교 결과 a b는 a가 b보다 나이가 많다는 뜻이다. 나이 관계는 전이된다. 예를 들어 a가 b보다 나이가 많고 b가 c보다 나이가 많다면, a가 c보다 나이가 많다는 것을 알 수 있다.

이제 여러 질의가 주어진다. 각 질의마다 두 사람 중 누가 더 나이가 많은지, 주어진 비교 결과만으로 판단하라. 두 이름이 같거나, 한쪽이 더 나이가 많다고 확정할 수 없으면 알 수 없는 것으로 본다.

첫째 줄에 사람의 수 N (N <= 1,000,000)과 비교 횟수 M (M <= 1,000,000)이 주어진다.

다음 M개 줄에는 a b가 주어진다. 이는 a가 b보다 나이가 많다는 뜻이다. 각 이름의 길이는 6바이트 이하이다.

그다음 줄에 질의의 수 Q (Q <= 20)가 주어진다.

다음 Q개 줄에는 a b가 주어진다. 각 질의는 a와 b 중 누가 더 나이가 많은지 묻는다.

질의 순서대로 답을 공백으로 구분해 한 줄에 출력한다.

한쪽이 더 나이가 많다는 것을 알 수 있으면 그 사람의 이름을 출력한다. 두 이름이 같거나 관계를 알 수 없으면 gg를 출력한다.