Git: Find the merge base

Compute what git merge-base --all prints.

What to build

A program that finds the best common ancestors of two commits.

Requirements

  • A common ancestor is reachable from both commits (a commit is reachable from itself). The best common ancestors are those that are not proper ancestors of any other common ancestor.
  • For each query print the best common ancestors sorted and separated by spaces, or none if the histories are unrelated.

Input

Line 1: c. Then c lines ID PARENT…. Then q and q lines X Y.

Output

q lines.

Constraints

c ≤ 500; q ≤ 50.

Example

Input:

5
a
b a
c b
f b
g f
2
c g
g b

Output:

b
b

Why it works

The best common ancestor is the latest point both histories share, which is exactly what a three-way merge must compare both sides against.

Examples

Example 1 · Input
5
a
b a
c b
f b
g f
2
c g
g b
Expected output
b
b
Example 2 · Input
2
x
y
1
x y
Expected output
none

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

Hints

Hint 1

Find the common ancestors: commits reachable from both tips.

Hint 2

Keep only those that are not an ancestor of another common ancestor; there can be more than one.

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())):
    x, y = input().split()
    common = reachable(x) & reachable(y)
    best = sorted(c for c in common if not any(c != o and c in reachable(o) for o in common))
    print(" ".join(best) if best else "none")

Lesson: Merging →