1075. Check Connectivity After Node Removal

Given an undirected graph with n nodes and edges, a node 'removed' to delete (along with all its incident edges), and two nodes u and v (both different from removed), determine whether u and v remain connected after the removal. Return true or false. The input is JSON {n, edges, removed, u, v}.

Input: JSON {n, edges, removed, u, v}.

Output: Boolean — true or false.

Examples

Input: {"n":5,"edges":[[0,1],[1,2],[2,3],[3,4]],"removed":2,"u":0,"v":4}
Output: false
Explanation: Removing 2 splits the chain.

Input: {"n":5,"edges":[[0,1],[1,2],[0,2],[2,3],[3,4]],"removed":1,"u":0,"v":4}
Output: true
Explanation: An alternate route remains.

Input: {"n":3,"edges":[[0,1],[1,2]],"removed":1,"u":0,"v":2}
Output: false
Explanation: The bridge node is gone.

Constraints

• 1<=n<=10^5
• u,v != removed

Asked by