982. Multi-Source BFS — Minimum Distance to Any Source

Given an undirected graph with n nodes, a list of edges, and a set of source nodes, return an array where entry i is the minimum number of edges from node i to the nearest source (0 if i is itself a source, -1 if unreachable from all sources). The input is JSON {n, edges, sources}.

Input: JSON {n, edges, sources}.

Output: Array — the minimum distance to any source per node.

Examples

Input: {"n":5,"edges":[[0,1],[0,2],[1,3],[2,4]],"sources":[3,4]}
Output: [2,1,1,0,0]
Explanation: Distance to the nearest of 3 or 4.

Input: {"n":3,"edges":[],"sources":[0,1,2]}
Output: [0,0,0]
Explanation: All are sources.

Input: {"n":4,"edges":[[0,1],[1,2],[2,3]],"sources":[0]}
Output: [0,1,2,3]
Explanation: Distances along the chain.

Constraints

• 1<=n<=10^5
• 1<=sources<=n
• undirected

Asked by