Git: What kind of merge?

Predict what git merge will do before running it.

What to build

A program that decides whether merging a branch is already up to date, a fast-forward or a true merge.

Requirements

  • For each query OURS THEIRS (two commit ids), print Already up to date. if THEIRS is reachable from OURS, else Fast-forward if OURS is reachable from THEIRS, else Merge made by the 'ort' strategy.

Input

Line 1: c. Then c lines ID PARENT…. Then q and q lines OURS THEIRS.

Output

q lines.

Constraints

c ≤ 1,000; q ≤ 100.

Example

Input:

4
a
b a
c b
f b
3
b c
c f
c b

Output:

Fast-forward
Merge made by the 'ort' strategy.
Already up to date.

Why it works

If the other side has nothing new, there is nothing to do; if our side has nothing new, our branch can jump to theirs; only when both have new work is a merge commit needed.

Examples

Example 1 · Input
4
a
b a
c b
f b
3
b c
c f
c b
Expected output
Fast-forward
Merge made by the 'ort' strategy.
Already up to date.
Example 2 · Input
1
a
1
a a
Expected output
Already up to date.

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Compute the set of commits reachable from each tip.

Hint 2

Check "already up to date" first: the other tip is reachable from ours (including equal).

Solution

Show one correct solution (try it yourself first)
parents = {}
for _ in range(int(input())):
    oid, *ps = input().split()
    parents[oid] = ps


def reachable(tip):
    seen, stack = set(), [tip]
    while stack:
        oid = stack.pop()
        if oid not in seen:
            seen.add(oid)
            stack.extend(parents[oid])
    return seen


for _ in range(int(input())):
    ours, theirs = input().split()
    if theirs in reachable(ours):
        print("Already up to date.")
    elif ours in reachable(theirs):
        print("Fast-forward")
    else:
        print("Merge made by the 'ort' strategy.")

Lesson: Merging →