/**
 * 競技プログラミング解答コード
 * 言語: C++23
 * 
 * 解法アプローチ:
 * 1. 岩井星人グラフの条件 (次数1と次数3がX個, 全ての葉から最寄りの次数3までの距離がL=Y-1) を満たすため、
 *    追加する辺によって次数分布と距離関係を調整します。
 * 2. 入力M != N-1 の場合は、最終的にN辺(1サイクル)を作る要件から即座にNoを出力します(孤立点対策含む)。
 *    ただし、孤立点がある場合は N頂点 N-1辺になりうるため、次数のGap解析で候補を絞ります。
 * 3. 候補モード:
 *    - Mode 11: 葉同士を結ぶ (Gap=2, X不変)
 *    - Mode 22: 次数2同士を結ぶ (Gap=2, X+2)
 *    - Mode 12: 葉と次数2を結ぶ (Gap=2, X+1)
 *    - Mode 01/02: 孤立点処理 (Gap=0)
 * 4. 距離条件の判定:
 *    - 既存の次数3頂点からの距離 `dist_old` をBFSで計算。
 *    - 条件を満たさない「悪い葉」を特定。
 *    - 「悪い葉」は、正しい距離Lの位置にある次数2頂点を次数3に昇格させることで救済する必要があります。
 *      この候補頂点は、葉から次数2のパスをL歩進んだ位置に一意に定まります(森構造のため)。
 *    - これにより候補探索を高速化し、全探索を回避します。
 * 5. 最終確認 (`check_final`):
 *    - 候補ペアに対して実際に辺を追加し、BFSで全葉の距離条件を確認します。
 */

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

const int INF = 1e9;
int N, M;
vector<vector<int>> adj;
vector<int> deg;
vector<int> dist_old;
vector<int> dist_to_leaf;

// 指定された葉から次数2の頂点のみを辿ってK歩進んだ頂点を返す
// パスが存在しない、分岐がある、次数条件を満たさない場合は-1
int get_node_at_dist_walk(int start, int K) {
    if (K == 0) return start;
    int curr = start;
    int prev = -1;
    for (int i = 0; i < K; ++i) {
        int found = -1;
        for (int nxt : adj[curr]) {
            if (nxt != prev) {
                found = nxt;
                break;
            }
        }
        if (found == -1) return -1;
        
        // 途中経路は次数2でなければならない (分岐なし)
        // 最終到達点は次数2でも3でも良いが、この関数の用途的に次数2を期待することが多い
        // ただし、startが次数1であることを前提とする
        // i < K-1 の間は次数2必須
        if (deg[found] > 2 && i < K - 1) return -1;
        
        prev = curr;
        curr = found;
    }
    return curr;
}

// 最終チェック
bool check_final(int u, int v, int target_X, int target_L) {
    // 既存の辺チェック
    for (int nxt : adj[u]) if (nxt == v) return false;
    
    deg[u]++; deg[v]++;
    adj[u].push_back(v);
    adj[v].push_back(u);
    
    bool valid = true;
    
    // 次数カウントとソース収集
    int cn1 = 0;
    vector<int> sources;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 1) cn1++;
        else if (deg[i] == 3) sources.push_back(i);
        else if (deg[i] > 3) valid = false;
    }
    
    if (valid && (cn1 != target_X || (int)sources.size() != target_X)) valid = false;
    
    if (valid) {
        static vector<int> d;
        if ((int)d.size() != N + 1) d.resize(N + 1);
        fill(d.begin(), d.end(), -1);
        
        queue<int> q;
        for (int s : sources) {
            d[s] = 0;
            q.push(s);
        }
        
        while (!q.empty()) {
            int curr = q.front(); q.pop();
            if (d[curr] >= target_L) continue; // 最短距離がLを超えても葉でなければ問題ないが、Lで打ち切り
            
            for (int nxt : adj[curr]) {
                if (d[nxt] == -1) {
                    d[nxt] = d[curr] + 1;
                    q.push(nxt);
                }
            }
        }
        
        for (int i = 1; i <= N; ++i) {
            if (deg[i] == 1) {
                if (d[i] != target_L) {
                    valid = false;
                    break;
                }
            }
        }
    }
    
    // 復元
    adj[u].pop_back();
    adj[v].pop_back();
    deg[u]--; deg[v]--;
    
    return valid;
}

void bfs_dist(const vector<int>& starts, vector<int>& res) {
    fill(res.begin(), res.end(), INF);
    queue<int> q;
    for (int u : starts) {
        res[u] = 0;
        q.push(u);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (res[v] == INF) {
                res[v] = res[u] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> N >> M)) return 0;
    
    adj.resize(N + 1);
    deg.resize(N + 1, 0);
    
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    
    if (M > N) { cout << "No" << endl; return 0; } // 辺過多
    
    // 次数超過チェック
    for (int i = 1; i <= N; ++i) if (deg[i] > 3) { cout << "No" << endl; return 0; }
    
    int n1 = 0, n3 = 0, n0 = 0;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 1) n1++;
        else if (deg[i] == 3) n3++;
        else if (deg[i] == 0) n0++;
    }
    
    int gap = n1 - n3;
    vector<pair<string, int>> candidates;
    
    if (n0 == 0) {
        if (gap == 2) {
            candidates.push_back({"11", n3});
            candidates.push_back({"12", n3 + 1});
            candidates.push_back({"22", n3 + 2});
        }
    } else if (n0 == 1) {
        if (gap == 0) {
            candidates.push_back({"01", n3});
            candidates.push_back({"02", n3 + 1});
        }
    }
    
    if (candidates.empty()) { cout << "No" << endl; return 0; }
    
    // Precalc distances
    vector<int> sources3, sources1;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 3) sources3.push_back(i);
        if (deg[i] == 1) sources1.push_back(i);
    }
    
    dist_old.resize(N + 1);
    dist_to_leaf.resize(N + 1);
    bfs_dist(sources3, dist_old);
    bfs_dist(sources1, dist_to_leaf);
    
    for (auto [mode, X] : candidates) {
        if (X <= 0 || N % X != 0) continue;
        int Y = N / X;
        if (Y < 2) continue;
        int L = Y - 1;
        
        if (mode == "11") {
            vector<int> bad;
            for (int l : sources1) if (dist_old[l] != L) bad.push_back(l);
            
            if (bad.size() == 2) {
                if (check_final(bad[0], bad[1], X, L)) { cout << "Yes" << endl; return 0; }
            } else if (bad.empty()) {
                if (sources1.size() >= 2) {
                    if (check_final(sources1[0], sources1[1], X, L)) { cout << "Yes" << endl; return 0; }
                }
            }
        }
        else if (mode == "22") {
            bool possible = true;
            vector<int> bad_leaves;
            for (int l : sources1) {
                if (dist_old[l] < L) { possible = false; break; }
                if (dist_old[l] != L) bad_leaves.push_back(l);
            }
            if (!possible) continue;
            
            set<int> targets;
            bool target_possible = true;
            for (int l : bad_leaves) {
                int t = get_node_at_dist_walk(l, L);
                if (t == -1) { target_possible = false; break; }
                targets.insert(t);
            }
            if (!target_possible) continue;
            if (targets.size() > 2) continue;
            
            vector<int> target_list(targets.begin(), targets.end());
            
            // 候補探索
            // targetsに含まれる頂点は必須。残りは valid_deg2 から選ぶ。
            // valid_deg2: deg=2 かつ dist_to_leaf >= L
            
            auto is_valid_v = [&](int v) {
                return deg[v] == 2 && dist_to_leaf[v] >= L;
            };
            
            if (target_list.size() == 2) {
                int u = target_list[0];
                int v = target_list[1];
                if (is_valid_v(u) && is_valid_v(v)) {
                    if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                }
            } else if (target_list.size() == 1) {
                int u = target_list[0];
                if (is_valid_v(u)) {
                    // v を探索
                    int count = 0;
                    for (int v = 1; v <= N; ++v) {
                        if (v != u && is_valid_v(v)) {
                            if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                            if (++count >= 50) break;
                        }
                    }
                }
            } else {
                // targetなし (全ての葉が良い状態) -> 任意のvalidペア
                vector<int> vs;
                for (int v = 1; v <= N; ++v) if (is_valid_v(v)) vs.push_back(v);
                int count = 0;
                for (size_t i = 0; i < vs.size(); ++i) {
                    for (size_t j = i + 1; j < vs.size(); ++j) {
                        if (check_final(vs[i], vs[j], X, L)) { cout << "Yes" << endl; return 0; }
                        if (++count >= 50) goto next_mode;
                    }
                }
            }
        }
        else if (mode == "12") {
            // dist_old < L な葉が2つ以上あれば救済不可 (uとして選べるのは1つだけ)
            vector<int> too_close;
            for (int l : sources1) if (dist_old[l] < L) too_close.push_back(l);
            if (too_close.size() > 1) continue;
            
            vector<int> potential_us;
            if (too_close.size() == 1) potential_us.push_back(too_close[0]);
            else {
                for (int l : sources1) if (dist_old[l] != L) potential_us.push_back(l);
                if (potential_us.size() > 50) potential_us.resize(50);
                // 正常な葉も少し試す
                int cnt = 0;
                for (int l : sources1) {
                    if (dist_old[l] == L) {
                        potential_us.push_back(l);
                        if (++cnt >= 10) break;
                    }
                }
            }
            
            for (int u : potential_us) {
                // u を取り除いたとき、他の悪い葉を救う v が必要
                // needed: dist_old > L or INF (dist_old < L はありえない、上でフィルタ済)
                vector<int> needed;
                for (int l : sources1) if (l != u && (dist_old[l] > L || dist_old[l] == INF)) needed.push_back(l);
                
                int req_v = -1;
                bool possible_u = true;
                
                for (int l : needed) {
                    // u 経由で解決可能か? (dist(l, u) == L - 1)
                    int t_u = get_node_at_dist_walk(l, L - 1);
                    if (t_u == u) continue; // u経由でOK
                    
                    // v 経由で解決必須 (dist(l, v) == L, v is ancestor)
                    int t_v = get_node_at_dist_walk(l, L);
                    if (t_v == -1) { possible_u = false; break; }
                    
                    if (req_v == -1) req_v = t_v;
                    else if (req_v != t_v) { possible_u = false; break; }
                }
                
                if (!possible_u) continue;
                
                if (req_v != -1) {
                    int v = req_v;
                    if (v != u && deg[v] == 2) {
                        if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                    }
                } else {
                    // 制約なし。任意のvalidなv
                    int count = 0;
                    for (int v = 1; v <= N; ++v) {
                        if (v != u && deg[v] == 2) {
                            // ヒューリスティック: dist_to_leaf >= L のものを優先
                            // ただし u が close な場合もあるので厳密には check_final 任せ
                            if (dist_to_leaf[v] >= L) {
                                if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                                if (++count >= 50) break;
                            }
                        }
                    }
                    // dist_to_leaf < L のものも少し試すべき？
                    // u が唯一近い葉ならばOKなケースがあるため
                    if (count < 10) {
                         for (int v = 1; v <= N; ++v) {
                            if (v != u && deg[v] == 2 && dist_to_leaf[v] < L) {
                                if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                                if (++count >= 60) break;
                            }
                        }
                    }
                }
            }
        }
        else if (mode == "01") {
            int iso = -1;
            for(int i=1; i<=N; ++i) if(deg[i]==0) { iso = i; break; }
            if(iso != -1) {
                // v は dist_old == L-1 である葉
                for (int v : sources1) {
                    if (dist_old[v] == L - 1) {
                        bool ok = true;
                        for (int l : sources1) if (l != v && dist_old[l] != L) { ok = false; break; }
                        if (ok && check_final(iso, v, X, L)) { cout << "Yes" << endl; return 0; }
                    }
                }
            }
        }
        else if (mode == "02") {
            int iso = -1;
            for(int i=1; i<=N; ++i) if(deg[i]==0) { iso = i; break; }
            if(iso != -1 && L == 1) {
                bool ok = true;
                for (int l : sources1) if (dist_old[l] != 1) { ok = false; break; }
                if (ok) {
                    int count = 0;
                    for (int v = 1; v <= N; ++v) {
                        if (deg[v] == 2) {
                            if (check_final(iso, v, X, L)) { cout << "Yes" << endl; return 0; }
                            if (++count >= 50) break;
                        }
                    }
                }
            }
        }
        
        next_mode:;
    }
    
    cout << "No" << endl;
    return 0;
}