Friend suggestions by mutual friends

A small social app has n users numbered 0..n-1 and an undirected list of friendships. For every user it wants to show exactly one "people you may know" suggestion.

Write recommend_friends(n: int, friendships: list[tuple[int, int]]) -> list[int] returning a list rec of length n, where rec[u] is chosen like this:

1. A candidate for u is any user v with v != u, v not already a friend of u, and at least one mutual friend (someone who is a friend of both).
2. Prefer the candidate with the most mutual friends with u.
3. Among candidates tied on that count, pick the smallest id.
4. If u has no candidates, rec[u] = -1.

n = 6
friendships = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (1, 4)]
recommend_friends(n, friendships)   # [3, 2, 1, 0, 0, -1]
# user 0: friends {1, 2}; 3 is reached through 1 and 2 (2 mutual), 4 through 1 (1 mutual) -> 3
# user 1: friends {0, 3, 4}; 2 shares 0 and 3 (2 mutual) -> 2
# user 4: friends {1, 3}; 0 shares 1, 2 shares 3 (1 mutual each) -> smaller id 0
# user 5: no friends at all -> -1

Details:

• Each friendship (a, b) has a != b and appears at most once (in either orientation).
• 1 <= n <= 5000, up to 25,000 friendships, and the graph is sparse.
• Counting mutual friends for every pair of users is too slow at that size: the work should depend on the friendships, not on n².