PT07Y - Is it a tree


You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.

Input

The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph (0 < N <= 10000, 0 <= M <= 20000). Next M lines contain M edges of that graph --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).

Output

Print YES if the given graph is a tree, otherwise print NO.

Example

Input:
3 2
1 2
2 3

Output:
YES

hide comments
sarkybastard: 2020-09-24 23:29:07

AND WHAT IF I DONT? YOUR PROBLEMS ARE NOT MY PROBLEMS.

kapilsukrit2: 2020-09-22 05:04:52

GUYS LISTEN! FOR TLE -> USE ADJACENCY LIST NOT MATRIX. SIMPLE DFS WORKS AS A CHARM!!

samiya_ahmed5: 2020-09-18 06:38:23

simple observation may help : 1 connected component and no cycle..:)

singhar: 2020-09-05 11:31:00

i submitted two solutions 1st for directed and second for undirected.Both got accepted.

jrseinc: 2020-08-19 10:37:15

easy disjoint set union problem

harry_shit: 2020-08-18 13:53:43

simple dfs will do the the work

saurabh_shinde: 2020-08-14 16:34:59

AC in one go!! Thanks to comment on connected component

adikrmishra_1: 2020-06-22 19:19:21

simple one using
no of connected compo ==1 && m=n-1

picchi_67: 2020-06-13 09:10:43

easy DSU problem...but you have to know what is tree...
1.must have all the nodes connected.
2.no cycle
3.edges are undirected.
4.must have one edge.

afaiyaz: 2020-06-11 12:44:01

If anyone getting TLE using recursive dfs just pass the vector to dfs function as a const reference.(in c++ ofcourse)

Last edit: 2020-06-11 12:44:44

Added by:Thanh-Vy Hua
Date:2007-03-28
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Co-author Amber