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

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

hide comments
2015-06-22 13:47:25
AC in 2nd go... read the method of finding connected components. Good question
2015-06-14 19:41:40 Sukeesh
input :
7 6
3 1
3 2
2 4
2 5
1 6
1 7

What would be the answer for this?
2015-06-11 21:59:22 Linus
Very good question ..learned a lot ...read this .... https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf .....The way here union find is described is just awesome .... my 25 !!!!!
2015-06-11 20:12:42 peeyush taneja
NIce question
2015-06-08 23:30:52 mayank
They are not checking for edge disconnectivity in graph (ie. already given m=n-1).Good problem though.
2015-06-05 10:18:35 Manish Sombansh
I am trying to solve this problem using union-find. but am getting TLE. Can anybody please tell me what's the error? My source code : http://ideone.com/EogUfW
2015-06-04 16:26:13 BRAIN
using dfs or bfs to check connect and using FindSet and Union of Kruskal algorithm to check circle
2015-05-29 17:52:14 Shubham Khilari
my first problem in graphs. solved in O(n^2).Did not use any stl or dfs bfs.Just try to find if there is a cycle or not..and then u r done.Executes in 0.09.Is there a faster way?

PS:
I got two WAs for using just int...so use long long int(that was my bad lol )
2015-05-26 10:42:53 Aman Agarwal
1st question of graph.. :)
2015-05-24 18:01:15
Just one graph traversal, no need to apply union find!!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.