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-08-22 23:09:42
awesome problem ..learned a lot !!!
2015-08-18 10:56:19 Vivek
if Using DFS, Don't use ADJ Matrix.It would result in O(v^2) time.
Go for DFS+ ADJList.
With Matrix,got TLE, With List Accepted.
2015-08-12 05:24:18 SangKuan
first i used visited array and got many errors,then is use two hash, colored and merge the edge got ac.no need
dfs or bfs, but i think union find is the best way

Last edit: 2015-08-12 05:24:51
2015-08-10 15:48:19 nadavishe
Very week test cases
2015-08-04 01:50:59 Saksham
no need of graph
2015-07-28 13:52:53 harkirat
how weak are the test cases?
My solution is completely wrong but got ac!
2015-07-05 18:13:25 Anurag Pasi
@Tanmay Kulshrestha I partially agree with u, when m==n-1 and still not a tree i.e it is cyclic , but i dont think there will b a totally disconnected node mayb there or mayb not u cant say..
i hope this helps
2015-07-03 14:37:39 Tanmay Kulshrestha
A confusion:
If m==n-1 and still it's not a tree, it means there is a cycle in the graph and for that to happen, there should be a totally disconnected node, right, because otherwise total edges will increase.
Please help !!

Last edit: 2015-07-03 14:38:18
2015-06-30 13:39:28 Anurag Pasi
Implementation of DFS by Adjacency list+STL 0.00 sec and 3.4Mb :)
There are total 3 conditions to check for a tree :
1) connected graph
2) non-cyclic or acyclic
3) n-1==m
but actually u hav to check only 2 conditions if u think :)

Last edit: 2015-06-30 13:41:24
2015-06-29 19:36:41 gamer496
@Sukeesh YES
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.