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
Murad Al Wajed: 2016-07-05 13:57:08

nice graph problem for biggener

geeta: 2016-07-02 22:36:02

Easy!!! did using BFS!!!

KD : 2016-06-28 20:26:21

DSU rocks!!!!!

ajay_raj: 2016-06-25 19:18:37

Last edit: 2016-07-01 03:48:29
baadshah_: 2016-06-22 11:19:46

tree should have edges n-1
use union find algo fo detecting cycle.

sam96: 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

and_roid: 2016-06-08 09:33:08

My first in graph theory!!..AC in one go!!
Thanx @dokz for your hints..:)

weramajstor: 2016-05-27 19:46:40

I have the right to vote finally vuhuuuuu!

Mihir Saxena: 2016-05-19 19:24:16

Getting sigsegv error, what can be the possibility?
Tried another approach, didn't create an array, instead used the union find algorithm directly on the edges and then in the end, checked the condition of connected graph, still got a WA

Last edit: 2016-05-19 20:02:58
Luis Herrera: 2016-05-13 22:20:50

Interesting problem.
Hints:
A graph is a tree if:
- It has no cycles
- It is connected


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