#include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) using namespace std; templatebool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; } using ll = long long; using ld = long double; using pi = pair; using pl = pair; using vi = vector; using vii = vector; using vl = vector; using vll = vector; const int inf = numeric_limits::max(); const ll infll = numeric_limits::max(); struct UFT{ vector par;//親 vector rank;//木の深さ vector size;//木の大きさ int n; UFT(int _n) { n = _n; par.resize(n); rank.assign(n,0); size.assign(n,0); rep(i,n){ par[i] = i; } } //xの根を返す int find(int x) { if(par[x] == x) return x; else return par[x] = find(par[x]); } //x,yを併合 void unite(int x,int y) { x = find(x); y = find(y); if(x == y) return; if(rank[x] < rank[y]){ par[x] = y; size[y] += size[x]; } else{ par[y] = x; size[x] += size[y]; if(rank[x] == rank[y]) rank[x]++; } } //x,yが同じグループにいるかどうかを返す bool same(int x,int y) { return find(x) == find(y); } //xの属する木のサイズを探す int usize(int x) { return size[find(x)]; } }; //**************************************** // Graph template //**************************************** // status of edge template struct Edge{ int from; int to; X cost; Edge() = default; Edge(int from, int to, X cost) : from(from), to(to), cost(cost) {} }; // status of node template struct Node{ int idx; vector> edge; Node() = default; explicit Node(int idx) : idx(idx) {} }; template class Graph{ private: int n; // number of node int m; // number of edge vector> node; void Init_Node() { rep(i,n) node.emplace_back(i); } public: explicit Graph(int n) : n(n) { Init_Node(); } // edges have no-weight Graph(int n, int m, vector from, vector to) : n(n), m(m) { Init_Node(); rep(i,m) { add_edge(from[i], to[i]); add_edge(to[i], from[i]); } } // edges have weight Graph(int n, int m, vector from, vector to, vector cost) : n(n), m(m) { Init_Node(); rep(i,m) { add_edge(from[i], to[i], cost[i]); add_edge(to[i], from[i], cost[i]); } } void add_edge(int from, int to, X cost = 1) { node[from].edge.emplace_back(from, to, cost); } // オイラー閉路があるか? bool EulerCheck() { bool res = true; rep(i,n) { int a = node[i].edge.size(); if(a % 2 == 1) res = false; } return res; } // s->tのオイラー路があるか? bool EulerCheck(int s, int t) { bool res = true; rep(i,n) { if(i == s || i == t) continue; int a = node[i].edge.size(); if(a % 2 == 1) res = false; } return res; } }; int main() { int n,m; cin >> n >> m; vi a(m), b(m); UFT uf(n); rep(i,m) { cin >> a[i] >> b[i]; uf.unite(a[i], b[i]); } Graph gp(n, m, a, b); rep(i,n) { rep(j,n) { if(i >= j) continue; if( !uf.same(i, j) ) { cout << "NO" << "\n"; return 0; } if(gp.EulerCheck(i, j)) { cout << "YES" << "\n"; return 0; } } } cout << "NO" << "\n"; return 0; }