978. Find Shortest Path in Unweighted Graph

Given an undirected unweighted graph with n nodes and a list of edges, return the length (number of edges) of the shortest path from src to dst, or -1 if dst is unreachable. The input is JSON {n, edges, src, dst}.

Input: JSON {n, edges, src, dst}.

Output: Integer — the shortest path length, or -1.

Examples

Input: {"n":5,"edges":[[0,1],[0,2],[1,3],[2,4]],"src":0,"dst":3}
Output: 2
Explanation: 0-1-3 is two edges.

Input: {"n":5,"edges":[[0,1],[2,3]],"src":0,"dst":3}
Output: -1
Explanation: Unreachable.

Input: {"n":1,"edges":[],"src":0,"dst":0}
Output: 0
Explanation: Same node.

Constraints

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

Asked by