Git: Ahead, behind or diverged?

Produce the line git status prints about the upstream branch.

What to build

A program that compares local branches with their upstreams and prints Git's status messages.

Requirements

  • For each query BRANCH LOCAL UPSTREAM print exactly one of: Your branch is up to date with 'origin/BRANCH'.; Your branch is ahead of 'origin/BRANCH' by N commit(s).; Your branch is behind 'origin/BRANCH' by N commit(s), and can be fast-forwarded.; or the two lines Your branch and 'origin/BRANCH' have diverged, and and have A and B different commits each, respectively. (A ahead, B behind).
  • Use commit for 1 and commits otherwise (the diverged message always says "commits").

Input

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

Output

The status lines.

Constraints

c ≤ 1,000; q ≤ 50.

Example

Input:

5
a
b a
c b
x b
y x
3
main c b
main b y
main c y

Output:

Your branch is ahead of 'origin/main' by 1 commit.
Your branch is behind 'origin/main' by 2 commits, and can be fast-forwarded.
Your branch and 'origin/main' have diverged,
and have 1 and 2 different commits each, respectively.

Why it works

Commits only one side can reach are the ones that side has and the other lacks, so the two counts say exactly what a push or a pull would have to transfer.

Examples

Example 1 · Input
5
a
b a
c b
x b
y x
3
main c b
main b y
main c y
Expected output
Your branch is ahead of 'origin/main' by 1 commit.
Your branch is behind 'origin/main' by 2 commits, and can be fast-forwarded.
Your branch and 'origin/main' have diverged,
and have 1 and 2 different commits each, respectively.
Example 2 · Input
1
a
1
dev a a
Expected output
Your branch is up to date with 'origin/dev'.

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

Hints

Hint 1

Ahead = commits reachable from the local tip but not the upstream tip; behind = the other way round.

Hint 2

Use 'commit' when the count is 1 and 'commits' otherwise.

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


def plural(n):
    return "commit" if n == 1 else "commits"


for _ in range(int(input())):
    branch, local, upstream = input().split()
    mine, theirs = reachable(local), reachable(upstream)
    ahead, behind = len(mine - theirs), len(theirs - mine)
    name = f"'origin/{branch}'"
    if ahead and behind:
        print(f"Your branch and {name} have diverged,")
        print(f"and have {ahead} and {behind} different commits each, respectively.")
    elif ahead:
        print(f"Your branch is ahead of {name} by {ahead} {plural(ahead)}.")
    elif behind:
        print(f"Your branch is behind {name} by {behind} {plural(behind)}, and can be fast-forwarded.")
    else:
        print(f"Your branch is up to date with {name}.")

Lesson: Remotes: clone, fetch, pull and push →