Given graph is a tree or not?

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


Solution:

A graph can be confirmed as a tree if and only if:

1)There are N-1 edges for N vertices
2)The Graph must be connected

#include <iostream>
#include <vector>
#include <set>
using namespace std;


#define MAX 100000
typedef vector<int> vi;
typedef vector<vi> vvi;

int N;
vvi W;//W stores the graph(Adjacency List)
vi V;//Array for storing whether a node is visited or not
set<int> s;// A set to store all the vertices.It is used to check if all
           // vertices are visited or not
void dfs(int i) 
{
        if(!V[i]) 
        { 
                vi::iterator it;
                V[i] = true;
                for(it=W[i].begin();it!=W[i].end();it++)
                        dfs(*it);
        }
} 

bool check_graph_connected_dfs(int s1) 
{ 
        int start_vertex = s1; 
        V = vi(MAX, false); 
        dfs(start_vertex);
        set<int>::iterator it; 
        for(it=s.begin();it!=s.end();it++)//check if any vertex in set is unvisited
        {
                if(V[*it]==0)
                        break;
        }
        if(it==s.end())
                return 1;
        else
                return 0;
}
int main()
{
        int v,e,v1,v2,temp;
        cin>>v>>e;
        vi::iterator it[MAX];
        if(e!=v-1)
        {
                cout<<"NO"<<endl;
                return 0;
        }
        W.resize(MAX);
        for(int i=0;i<MAX;i++)
        {
                it[i]=W[i].begin();
        }
        for(int i=0;i<e;i++)
        {
                cin>>v1>>v2;
                s.insert(v1);
                s.insert(v2);
                temp=v1;
                it[v1]=W[v1].insert(it[v1],v2); 
                it[v2]=W[v2].insert(it[v2],v1); 
        }
        if(check_graph_connected_dfs(temp))
                cout<<"YES"<<endl;
        else
                cout<<"NO"<<endl;
        return 0;
}