PT07Y

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

#include <iostream>
#include <vector>

using namespace std;

int root(int a, vector<int> &id) {  
    while (a != id[a]) {
        id[a] = id[id[a]];
        a = id[a];
    }
    return a;
}

bool isConnected(int a, int b, vector<int> &id) {  
    return (root(a, id) == root(b, id));
}

void Union(int a, int b, vector<int> &id, vector<int> &size) {  
    int roota = root(a,id);
    int rootb = root(b,id);
    if (size[roota] < size[rootb]) {
        id[roota] = rootb;
        size[rootb] += size[roota];
    } else {
        id[rootb] = roota;
        size[roota] += size[rootb];
    }
    return;
}

bool isATree(int N, vector<pair<int, int> > edges) {  
    vector<int> id(N),
                sz(N,1);
    for (int i = 0; i < N; ++i) {
        id[i] = i;
    }
    for (int i = 0; i < edges.size(); ++i) {
        if (isConnected(edges[i].first, edges[i].second, id)) {
            return false;
        } else {
            Union(edges[i].first, edges[i].second, id, sz);
        }
    }
    return true;
}

int main() {  
    int N, M;
    cin >> N >> M;
    vector<pair<int, int> > edges(M);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        edges[i] = make_pair(a,b);
    }

    if (isATree(N, edges)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}