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
2016-08-07 13:53:11
Do NOT use spoj toolkit for this one!
2016-07-26 05:46:46
I used union-find tree and I got 0.00 sec!
2016-07-12 13:58:54
I guess the test cases are weak.My naive solution also got accepted.
2016-07-05 13:57:08 Murad Al Wajed
nice graph problem for biggener
2016-07-02 22:36:02 geeta
Easy!!! did using BFS!!!
2016-06-28 20:26:21 KD
DSU rocks!!!!!
2016-06-22 11:19:46
tree should have edges n-1
use union find algo fo detecting cycle.
2016-06-10 18:18:03
HINT : A graph is a cycle if it no. of connected components=1 and edges = nodes-1
Source : https://en.wikipedia.org/wiki/Tree_%28graph_theory%29
2016-06-08 09:33:08
My first in graph theory!!..AC in one go!!
Thanx @dokz for your hints..:)

2016-05-27 19:46:40
I have the right to vote finally vuhuuuuu!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.