Shortest Chain of Introductions

At a conference, guest i already knows the guests listed in friends[i] (guests are labelled 0 .. n-1 with n = len(friends)). Acquaintance is mutual: if j is in friends[i] then i is in friends[j]. Guest a wants to meet guest b through a chain of introductions, where each link in the chain is a pair of guests who already know each other.

Return the smallest number of links in such a chain, 0 if a == b, or -1 if no chain exists.

Examples

Input:  friends = [[1,2],[0,3],[0],[1,4],[3]], a = 2, b = 4
Output: 4
Explanation: 2 - 0 - 1 - 3 - 4 uses four links.

    2 --- 0 --- 1 --- 3 --- 4

Input:  friends = [[1],[0],[]], a = 0, b = 2
Output: -1
Explanation: guest 2 knows nobody.

Constraints

• 1 <= n <= 10**4, total list length at most 5 * 10**4
• 0 <= a, b < n; lists contain no duplicates and no self-references.
• Target O(V + E) time.

Goals

• Run a BFS directly on a given adjacency list
• Report the hop count of the first time the target is reached
• Handle the same-person and unreachable cases