1018. Check if Graph is Tree

Given an undirected graph with n nodes and a list of edges, determine whether it forms a tree — connected and acyclic (equivalently, connected with exactly n-1 edges). Return true or false. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Boolean — true or false.

Examples

Input: {"n":4,"edges":[[0,1],[0,2],[0,3]]}
Output: true
Explanation: Connected and acyclic.

Input: {"n":4,"edges":[[0,1],[1,2],[2,0]]}
Output: false
Explanation: Has a cycle and is disconnected.

Input: {"n":1,"edges":[]}
Output: true
Explanation: A single node is a tree.

Constraints

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

Asked by