1011. Check if Two Nodes are in Same Component

Given an undirected graph with n nodes and a list of edges, plus a list of queries [u, v], return for each query whether u and v belong to the same connected component. Return the boolean answers as an array in order. The input is JSON {n, edges, queries}.

Input: JSON {n, edges, queries}.

Output: Array — a boolean per query.

Examples

Input: {"n":5,"edges":[[0,1],[2,3]],"queries":[[0,1],[1,2],[2,3]]}
Output: [true,false,true]
Explanation: Component membership per query.

Input: {"n":3,"edges":[],"queries":[[0,0],[0,1]]}
Output: [true,false]
Explanation: Self is same; others differ.

Input: {"n":2,"edges":[[0,1]],"queries":[[0,1]]}
Output: [true]
Explanation: Connected pair.

Constraints

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

Asked by