Git: Which branches contain a commit?

Answer the question git branch --contains answers.

What to build

A program that lists the branches whose history includes a given commit.

Requirements

  • Commits are given with their parents; branches with their tip commits.
  • For each query print ID: BRANCH BRANCH … with the branch names sorted, or ID: none.

Input

Line 1: c. Then c lines ID PARENT… (no parents for a root). Then b and b lines NAME TIP. Then q and q commit ids.

Output

q lines.

Constraints

c ≤ 1,000; b ≤ 50; q ≤ 100.

Example

Input:

4
a
b a
c b
f b
2
main c
feature f
3
a
c
f

Output:

a: feature main
c: main
f: feature

Why it works

A branch's history is everything reachable from its tip, so a commit belongs to the branches from whose tips it can be reached.

Examples

Example 1 · Input
4
a
b a
c b
f b
2
main c
feature f
3
a
c
f
Expected output
a: feature main
c: main
f: feature
Example 2 · Input
2
a
x
1
main a
1
x
Expected output
x: none

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

Hints

Hint 1

For each branch, search from its tip through parent links and collect every reachable commit.

Hint 2

A commit is contained in a branch if it is reachable from the branch's tip, including the tip itself.

Solution

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


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


history = {name: reachable(tip) for name, tip in branches.items()}
for _ in range(int(input())):
    oid = input().strip()
    names = sorted(name for name, seen in history.items() if oid in seen)
    print(f"{oid}: " + (" ".join(names) if names else "none"))

Lesson: Branches, HEAD and revision names →