Node with Maximum Common Neighbors

Problem Given an undirected graph with nodes 0 .. n-1, for each node find another node such that (a) the two are not directly connected by an edge, and (b) they share the maximum number of common neighbours. If several candidates tie, pick the one with the smallest index.

Input / Output

• Input: integer n and an edge list (or adjacency list) of an undirected graph.
• Output: an array ans of length n, where ans[u] is the best partner node for u, or -1 if no valid candidate exists.

Constraints

• n < 10^5.
• Each node has at most 15 neighbours — this degree bound is the crux of the problem.
• The partner must not be u itself and must not be adjacent to u.

Example

• Path graph 0-1-2-3: for node 0, node 2 shares the common neighbour 1 and is not adjacent to 0, so ans[0] = 2.
• Tricky case: a candidate reachable in two hops may nonetheless be directly connected to u (a triangle), and must be skipped despite a high common-neighbour count. Also, a node whose 2-hop set is entirely adjacent to it has no valid partner → -1.