Graph Valid Tree

Given n nodes and a list of undirected edges, print true if the edges form a valid tree (fully connected, no cycles), false otherwise.

Example

Input: n = 5, edges (0,1) (0,2) (0,3) (1,4) Output: true

Approach

A valid tree on n nodes has exactly n - 1 edges — any more guarantees a cycle, any fewer guarantees disconnection, so that's a free first check. Then Union-Find confirms the rest: process each edge, and if any union call fails (the two endpoints were already connected), that edge creates a cycle, so it can't be a tree.

Input format

Line 1: n Line 2: number of edges E Next E lines: a b

Print true or false.