Age Relations

Jimin has a special ability: when looking at two people, Jimin can tell which one is older. Using this ability, Jimin obtained M comparison results.

Each comparison a b means that a is older than b. Age relations are transitive. For example, if a is older than b and b is older than c, then a is older than c.

You are given several queries. For each query, determine which of the two people is older using only the given comparison results. If the two names are the same, or if neither side can be determined to be older, the answer is unknown.

The first line contains the number of people N (N <= 1,000,000) and the number of comparisons M (M <= 1,000,000).

Each of the next M lines contains a b, meaning that a is older than b. Each name is at most 6 bytes long.

The next line contains the number of queries Q (Q <= 20).

Each of the next Q lines contains a b. The query asks which of a and b is older.

Print the answers in query order on one line, separated by spaces.

If one person can be determined to be older, print that person's name. If the two names are the same or the relation cannot be determined, print gg.