#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <unistd.h>
#include <ext/pb_ds/assoc_container.hpp>

#ifdef ATCODER
#include <atcoder/all>
#endif

using namespace std;
using namespace __gnu_pbds;
#ifdef ATCODER
using namespace atcoder;
#endif

using i32 = int;
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using ld = long double;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
using pii = pair<i32, i32>;
using pll = pair<i64, i64>;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int INF32 = (1 << 30);
constexpr i64 INF64 = (i64(1) << 60);

struct Scanner {
    static constexpr size_t BUFSIZE = 1 << 20;
    int fd;
    size_t idx;
    size_t size;
    array<char, BUFSIZE> buf;

    Scanner(int fd_ = 0) : fd(fd_), idx(0), size(0) {}

    inline void refill() {
        size = ::read(fd, buf.data(), BUFSIZE);
        idx = 0;
    }

    inline char getch() {
        if (idx >= size) {
            refill();
            if (size == 0) return '\0';
        }
        return buf[idx++];
    }

    inline bool skip_space() {
        char c = getch();
        while (c <= ' ' && c != '\0') c = getch();
        if (c == '\0') return false;
        idx--;
        return true;
    }

    template<class T>
    bool read_signed(T &x) {
        if (!skip_space()) {
            x = 0;
            return false;
        }
        char c = getch();
        bool neg = false;
        if (c == '-') {
            neg = true;
            c = getch();
        }
        T val = 0;
        while ('0' <= c && c <= '9') {
            val = val * 10 + (c - '0');
            c = getch();
        }
        x = neg ? -val : val;
        return true;
    }

    template<class T>
    bool read_unsigned(T &x) {
        if (!skip_space()) {
            x = 0;
            return false;
        }
        char c = getch();
        T val = 0;
        while ('0' <= c && c <= '9') {
            val = val * 10 + (c - '0');
            c = getch();
        }
        x = val;
        return true;
    }

    bool read(i32 &x) { return read_signed<i32>(x); }
    bool read(i64 &x) { return read_signed<i64>(x); }
    bool read(u32 &x) { return read_unsigned<u32>(x); }
    bool read(u64 &x) { return read_unsigned<u64>(x); }
    template<class T, class U>
    bool read(T &x, U &y) { return read(x) && read(y); }
};

struct Printer {
    static constexpr size_t BUFSIZE = 1 << 20;
    int fd;
    size_t idx;
    array<char, BUFSIZE> buf;

    Printer(int fd_ = 1) : fd(fd_), idx(0) {}

    ~Printer() {
        flush();
    }

    inline void flush() {
        if (idx) {
            ::write(fd, buf.data(), idx);
            idx = 0;
        }
    }

    inline void put_char(char c) {
        if (idx == BUFSIZE) flush();
        buf[idx++] = c;
    }

    void write_str(string_view s) {
        for (char c : s) put_char(c);
    }

    template<class T>
    void print(const T &x) {
        if constexpr (is_same_v<T, string>) write_str(x);
        else if constexpr (is_integral_v<T>) {
            if (x < 0) { put_char('-'); write_unsigned(-x); }
            else write_unsigned(x);
        } else write_str("Printer Error");
        put_char('\n');
    }

    template<class T>
    void write_unsigned(T x) {
        if (x == 0) { put_char('0'); return; }
        char s[64]; int n = 0;
        while (x > 0) { s[n++] = char('0' + (x % 10)); x /= 10; }
        while (n--) put_char(s[n]);
    }
};

Scanner in;
Printer out;

#define rep(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define repi(i, a, b) for (i32 i = (i32)(a); i < (i32)(b); ++i)
#define sz(x) ((i32)(x).size())
#define all(x) begin(x), end(x)

template<class F>
struct RecLambda {
    F f;
    RecLambda(F f_) : f(move(f_)) {}
    template<class... Args>
    decltype(auto) operator()(Args &&...args) const {
        return f(*this, forward<Args>(args)...);
    }
};

// Main Solver
void solve() {
    int N, M;
    in.read(N, M);
    VV<int> adj(N);
    V<int> deg(N, 0);
    rep(i, M) {
        int u, v; in.read(u, v); --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++; deg[v]++;
    }

    // Basic constraints check
    if (M != N - 1) { out.print("No"); return; }
    rep(i, N) if(deg[i] > 3) { out.print("No"); return; }

    int C1 = 0, C2 = 0, C3 = 0;
    rep(i, N) {
        if(deg[i] == 1) C1++;
        else if(deg[i] == 2) C2++;
        else if(deg[i] == 3) C3++;
    }

    // Helper BFS to compute distances from a set of sources
    auto bfs_multi = [&](const V<int>& sources) -> V<int> {
        V<int> d(N, -1);
        queue<int> q;
        for(int s : sources) {
            d[s] = 0; q.push(s);
        }
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int v : adj[u]){
                if(d[v] == -1){
                    d[v] = d[u] + 1;
                    q.push(v);
                }
            }
        }
        return d;
    };

    V<int> leaves, deg3s;
    rep(i, N) {
        if(deg[i] == 1) leaves.push_back(i);
        if(deg[i] == 3) deg3s.push_back(i);
    }

    V<int> min_dist_leaf = bfs_multi(leaves);
    V<int> min_dist_deg3 = bfs_multi(deg3s);

    // Group nodes by degree for fast candidate lookup
    V<V<int>> nodes_by_deg(4);
    rep(i, N) nodes_by_deg[deg[i]].push_back(i);

    // Iterate over possible Y
    // Y >= 2 because Y-1 >= 1 (distance). 
    // X = N/Y >= 3.
    for (int Y = 2; Y * 3 <= N; ++Y) {
        if (N % Y != 0) continue;
        int X = N / Y;
        
        // Target counts
        // Deg 1: X
        // Deg 2: X(Y - 2)
        // Deg 3: X
        
        int dC1 = X - C1;
        int dC2 = X * (Y - 2) - C2;
        int dC3 = X - C3;
        
        V<pii> valid_pair_types;
        rep(t1, 3) rep(t2, 3) {
            if (t1 > t2) continue;
            // simulate delta
            int c1 = 0, c2 = 0, c3 = 0;
            auto sim = [&](int t) {
                if(t == 0) c1++;
                if(t == 1) { c1--; c2++; }
                if(t == 2) { c2--; c3++; }
            };
            sim(t1); sim(t2);
            if (c1 == dC1 && c2 == dC2 && c3 == dC3) {
                valid_pair_types.push_back({t1, t2});
            }
        }
        
        if (valid_pair_types.empty()) continue;

        // Identify Bad Leaves for this Y
        V<int> bad_leaves;
        for(int l : leaves) {
            int d = min_dist_deg3[l];
            if (d == -1 || d != Y - 1) {
                bad_leaves.push_back(l);
            }
        }

        // Helper check for safety
        auto is_safe = [&](int u, int v) -> bool {
            bool u_new3 = (deg[u] == 2);
            bool v_new3 = (deg[v] == 2);
            // Check 1: New deg 3s shouldn't be too close to any leaf
            if (u_new3 && min_dist_leaf[u] != -1 && min_dist_leaf[u] < Y - 1) return false;
            if (v_new3 && min_dist_leaf[v] != -1 && min_dist_leaf[v] < Y - 1) return false;
            // Check 2: Shortcut to old deg 3
            if (min_dist_leaf[u] != -1 && min_dist_deg3[v] != -1) {
                 if (min_dist_leaf[u] + 1 + min_dist_deg3[v] < Y - 1) return false;
            }
            if (min_dist_leaf[v] != -1 && min_dist_deg3[u] != -1) {
                 if (min_dist_leaf[v] + 1 + min_dist_deg3[u] < Y - 1) return false;
            }
            // Check 3: Edge existence
            for(int x : adj[u]) if(x == v) return false;
            return true;
        };

        for(auto [t1, t2] : valid_pair_types) {
            const V<int>& U_cand = nodes_by_deg[t1];
            const V<int>& V_cand = nodes_by_deg[t2];
            if (U_cand.empty() || V_cand.empty()) continue;

            if (!bad_leaves.empty()) {
                int l = bad_leaves[0];
                V<int> dist_l = bfs_multi({l});
                V<pii> candidates;

                // Try to construct valid pairs fixing l
                // Method A: u becomes deg 3, dist(l, u) == Y - 1
                if (t1 == 2) {
                    for(int u : U_cand) {
                        if (dist_l[u] == Y - 1) {
                            if (min_dist_leaf[u] != -1 && min_dist_leaf[u] < Y - 1) continue; 
                            int limit = 0;
                            for(int v : V_cand) {
                                if (u == v) continue;
                                if (is_safe(u, v)) {
                                    candidates.push_back({u, v});
                                    if(++limit > 80) break;
                                }
                            }
                        }
                    }
                }
                // Method B: v becomes deg 3, dist(l, u) + 1 == Y - 1 -> dist(l, u) = Y - 2
                if (t2 == 2) {
                    for(int u : U_cand) {
                         if (dist_l[u] == Y - 2) {
                             int limit = 0;
                             for(int v : V_cand) {
                                 if (u == v) continue;
                                 if (is_safe(u, v)) {
                                     candidates.push_back({u, v});
                                     if(++limit > 80) break;
                                 }
                             }
                        }
                    }
                }
                // Method C: Connect to old deg 3, dist(l, u) + 1 + dist(v, deg3) == Y - 1
                for(int u : U_cand) {
                    if (dist_l[u] != -1 && dist_l[u] <= Y - 2) {
                        int rem = Y - 2 - dist_l[u];
                        int limit = 0;
                        for(int v : V_cand) {
                             if (u == v) continue;
                             if (min_dist_deg3[v] == rem) {
                                 if (is_safe(u, v)) {
                                     candidates.push_back({u, v});
                                     if (++limit > 80) break;
                                 }
                             }
                        }
                        if (candidates.size() > 500) break;
                    }
                }
                
                // Also check symmetric if t1 != t2? Handled by loop or candidates generation?
                // The above assumes u has type t1, v has type t2.
                // We also need u has type t2, v has type t1.
                if (t1 != t2) {
                     // Same logic with swapped roles
                     // Or just rely on outer loop iterating all types?
                     // Outer loop iterates t1 <= t2. So we must check swapped here or ensure logic covers it.
                     // The logic above generates candidates {u, v} where deg[u]=t1, deg[v]=t2.
                     // If we swap u,v, we get pair with deg[u]=t2, deg[v]=t1.
                     // We need to implement swapped logic too? 
                     // Actually, Method A checks if t1==2 (u becomes 3).
                     // Method B checks if t2==2 (v becomes 3).
                     // This covers asymmetrical roles.
                     // Method C iterates u in t1, v in t2.
                     // We need to also iterate u in t2, v in t1 for Method C?
                     // Yes.
                     const V<int>& U2 = nodes_by_deg[t2];
                     const V<int>& V2 = nodes_by_deg[t1];
                     
                     // Method C swapped
                     for(int u : U2) {
                        if (dist_l[u] != -1 && dist_l[u] <= Y - 2) {
                            int rem = Y - 2 - dist_l[u];
                            int limit = 0;
                            for(int v : V2) {
                                 if (u == v) continue;
                                 if (min_dist_deg3[v] == rem) {
                                     if (is_safe(u, v)) {
                                         candidates.push_back({u, v});
                                         if (++limit > 80) break;
                                     }
                                 }
                            }
                            if (candidates.size() > 500) break;
                        }
                    }
                }

                for(auto [u, v] : candidates) {
                    bool u_becomes_3 = (deg[u] == 2);
                    bool v_becomes_3 = (deg[v] == 2);
                    V<int> d_u = bfs_multi({u});
                    V<int> d_v = bfs_multi({v});
                    bool ok = true;
                    for(int bl : bad_leaves) {
                         int d_new = INF32;
                         if (min_dist_deg3[bl] != -1) d_new = min_dist_deg3[bl];
                         if (u_becomes_3 && d_u[bl] != -1) d_new = min(d_new, d_u[bl]);
                         if (v_becomes_3 && d_v[bl] != -1) d_new = min(d_new, d_v[bl]);
                         if (d_u[bl] != -1 && min_dist_deg3[v] != -1) 
                             d_new = min(d_new, d_u[bl] + 1 + min_dist_deg3[v]);
                         if (d_v[bl] != -1 && min_dist_deg3[u] != -1)
                             d_new = min(d_new, d_v[bl] + 1 + min_dist_deg3[u]);
                         if (d_new != Y - 1) { ok = false; break; }
                    }
                    if (ok) { out.print("Yes"); return; }
                }
            } else {
                // No bad leaves, just find safe pair
                int count = 0;
                for(int u : U_cand) {
                    for(int v : V_cand) {
                        if (u == v) continue;
                        if (is_safe(u, v)) {
                            out.print("Yes");
                            return;
                        }
                        if (++count > 500) break;
                    }
                    if (count > 500) break;
                }
            }
        }
    }

    out.print("No");
}

int main() {
    solve();
    return 0;
}