974. BFS Traversal of Undirected Graph

Given an undirected graph with n nodes and a list of edges, perform a breadth-first search from a given start node, always visiting neighbors in ascending order. Return the order in which nodes are first visited as an array. The input is JSON {n, edges, start}.

Input: JSON {n, edges, start}.

Output: Array — the BFS visitation order.

Examples

Input: {"n":5,"edges":[[0,1],[0,2],[1,3],[2,4]],"start":0}
Output: [0,1,2,3,4]
Explanation: Level-order from node 0.

Input: {"n":1,"edges":[],"start":0}
Output: [0]
Explanation: Single node.

Input: {"n":4,"edges":[[0,1],[2,3]],"start":2}
Output: [2,3]
Explanation: Only the component of 2.

Constraints

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

Asked by