Longest path in a DAG from an edge list

You are given a directed acyclic graph as a list of edges. Each edge is a pair [u, v] of node names and means there is an edge from u to v. A node exists only if it appears in at least one edge.

Implement:

def longest_path(edges: list[tuple[str, str]]) -> list[str]:
    ...

Return the nodes of a longest path in the graph, in order from its first node to its last. Path length is the number of edges on it. If several paths share the longest length, return the lexicographically smallest list of node names. If edges is empty, return [].

Constraints

• 0 <= len(edges) <= 10^4
• Node names are 1 to 5 uppercase letters or digits.
• The graph has no cycles. The same edge may appear more than once.

Example 1

edges  = [["A","B"], ["B","C"], ["A","C"], ["C","D"]]
output = ["A","B","C","D"]

The edge A -> C is a shortcut; the longest path goes through B and has 3 edges.

Example 2

edges  = [["S","M"], ["S","K"], ["M","T"], ["K","T"]]
output = ["S","K","T"]

S -> M -> T and S -> K -> T both have 2 edges. ["S","K","T"] is lexicographically smaller.

Be ready to discuss what should happen if the input does contain a cycle.

Reconstructed from the reported question; details may differ from what interviewers ask.