/**
 * 解法アプローチ:
 * 1. 入力グラフは N 頂点 M 辺で、1辺追加して岩井星人グラフ（N頂点 N辺、次数条件、距離条件）を作る必要がある。
 * 2. 最終的に N 辺になるため、入力は M = N - 1（森）であることが必要条件。
 * 3. 岩井星人グラフの条件:
 *    - 次数1の頂点数 = 次数3の頂点数 = X
 *    - 全ての次数1頂点から、最も近い次数3頂点への距離が Y-1 (L) である。
 * 4. 辺追加による次数変化と X の整合性を確認するため、Gap = Count(Deg1) - Count(Deg3) に着目する。
 *    - Gap = 2 の場合 (通常の木構造など):
 *      - Mode 11: 葉と葉を結ぶ (X = C3)。
 *      - Mode 12: 葉と次数2を結ぶ (X = C3 + 1)。
 *      - Mode 22: 次数2同士を結ぶ (X = C3 + 2)。
 *    - Gap = 0 かつ 孤立点ありの場合:
 *      - Mode 01, 02 を試す。
 * 5. 各モードについて、距離条件 L を満たす候補ペアを探索する。
 *    - 距離条件を満たさない「悪い葉」を特定し、それらを被覆できる候補頂点を集合交差や探索で絞り込む。
 *    - N が最大 3x10^5 なので、候補全探索は不可。必要条件（距離 L、葉に近づきすぎない等）で候補を絞り、
 *      最終確認 (check_final) で実際にBFSを行い判定する。
 */

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

using namespace std;

// 定数・グローバル変数
const int INF = 1e9;
int N, M;
vector<vector<int>> adj;
vector<int> deg;

// 距離計算用 (BFS)
void get_dists(const vector<int>& sources, vector<int>& d) {
    fill(d.begin(), d.end(), INF);
    queue<int> q;
    for (int u : sources) {
        d[u] = 0;
        q.push(u);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (d[v] == INF) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}

// 2点間距離 (BFS)
int get_single_dist(int s, int t) {
    if (s == t) return 0;
    queue<pair<int, int>> q;
    q.push({s, 0});
    vector<int> visited_dist(N + 1, -1);
    visited_dist[s] = 0;
    
    while (!q.empty()) {
        auto [u, d] = q.front(); q.pop();
        if (u == t) return d;
        if (d >= visited_dist[s] + N) continue; // Safety break, though BFS finds shortest
        
        for (int v : adj[u]) {
            if (visited_dist[v] == -1) {
                visited_dist[v] = d + 1;
                q.push({v, d + 1});
            }
        }
    }
    return INF;
}

// 最終チェック: 辺 (u, v) を追加して条件を満たすか
bool check_final(int u, int v, int target_X, int target_L) {
    // 辺追加
    deg[u]++; deg[v]++;
    adj[u].push_back(v);
    adj[v].push_back(u);
    
    // 次数3以上の頂点を始点にBFS
    vector<int> sources;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 3) sources.push_back(i);
        else if (deg[i] > 3) { // 次数超過チェック
            deg[u]--; deg[v]--; adj[u].pop_back(); adj[v].pop_back();
            return false; 
        }
    }
    
    // Xの一致確認
    int n1 = 0;
    for (int i = 1; i <= N; ++i) if (deg[i] == 1) n1++;
    if (n1 != target_X || (int)sources.size() != target_X) {
        deg[u]--; deg[v]--; adj[u].pop_back(); adj[v].pop_back();
        return false;
    }
    
    vector<int> d(N + 1, -1);
    queue<int> q;
    for (int s : sources) {
        d[s] = 0;
        q.push(s);
    }
    
    bool valid = true;
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        // Lより深い探索は判定に不要だが、L未満の葉を見つけるために必要
        // ただし最適化として L+1 程度で打ち切る手もあるが、正確性重視
        if (d[curr] > target_L) continue; 
        
        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;
            }
        }
    }
    
    // 戻す
    deg[u]--; deg[v]--;
    adj[u].pop_back(); adj[v].pop_back();
    return valid;
}

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]++;
    }
    
    // 次数超過チェック
    for (int d : deg) if (d > 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; }
    
    // 前計算: 既存の次数3からの距離
    vector<int> dist_old(N + 1);
    vector<int> sources;
    for (int i = 1; i <= N; ++i) if (deg[i] == 3) sources.push_back(i);
    get_dists(sources, dist_old);
    
    // 前計算: 最寄りの葉までの距離
    vector<int> leaves;
    for (int i = 1; i <= N; ++i) if (deg[i] == 1) leaves.push_back(i);
    vector<int> dist_to_leaf(N + 1);
    get_dists(leaves, 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 : leaves) 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 (leaves.size() >= 2) {
                    if (check_final(leaves[0], leaves[1], X, L)) { cout << "Yes" << endl; return 0; }
                }
            }
        }
        else if (mode == "22") {
            // 条件: dist_old >= L であること（近すぎる葉は救えない）
            bool possible = true;
            for (int l : leaves) if (dist_old[l] < L) { possible = false; break; }
            if (!possible) continue;
            
            vector<int> bad_leaves;
            for (int l : leaves) if (dist_old[l] != L) bad_leaves.push_back(l);
            
            // 悪い葉をカバーできる候補頂点集合を計算
            vector<set<int>> cover_sets;
            for (int l : bad_leaves) {
                set<int> s;
                // BFSで距離Lの次数2頂点を探す
                queue<pair<int, int>> q;
                q.push({l, 0});
                set<int> vis; vis.insert(l);
                while (!q.empty()) {
                    auto [u, d] = q.front(); q.pop();
                    if (d == L) {
                        if (deg[u] == 2) s.insert(u);
                        continue; 
                    }
                    if (d < L) {
                        for (int v : adj[u]) {
                            if (vis.find(v) == vis.end()) {
                                vis.insert(v);
                                q.push({v, d + 1});
                            }
                        }
                    }
                }
                if (s.empty()) { possible = false; break; }
                cover_sets.push_back(s);
            }
            if (!possible) continue;
            
            // 有効な次数2頂点 (他の葉に近すぎない)
            vector<int> valid_deg2;
            for (int i = 1; i <= N; ++i) {
                if (deg[i] == 2 && dist_to_leaf[i] >= L) valid_deg2.push_back(i);
            }
            set<int> valid_set(valid_deg2.begin(), valid_deg2.end());
            
            // cover_sets を valid_set でフィルタリング
            vector<set<int>> filtered_sets;
            for (const auto& s : cover_sets) {
                set<int> inter;
                for (int x : s) if (valid_set.count(x)) inter.insert(x);
                if (inter.empty()) { possible = false; break; }
                filtered_sets.push_back(inter);
            }
            if (!possible) continue;
            
            if (filtered_sets.empty()) {
                if (valid_deg2.size() >= 2) {
                    if (check_final(valid_deg2[0], valid_deg2[1], X, L)) { cout << "Yes" << endl; return 0; }
                }
            } else {
                sort(filtered_sets.begin(), filtered_sets.end(), [](const set<int>& a, const set<int>& b){
                    return a.size() < b.size();
                });
                
                // Set Coverの探索 (u を最小集合から選ぶ)
                int limit = 0;
                for (int u : filtered_sets[0]) {
                    if (++limit > 50) break;
                    
                    vector<int> uncovered_idx;
                    for (size_t i = 0; i < filtered_sets.size(); ++i) {
                        if (filtered_sets[i].find(u) == filtered_sets[i].end()) uncovered_idx.push_back(i);
                    }
                    
                    if (uncovered_idx.empty()) {
                        for (int v : valid_deg2) {
                            if (v != u) {
                                if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                                break; 
                            }
                        }
                    } else {
                        set<int> cand_v = filtered_sets[uncovered_idx[0]];
                        for (size_t k = 1; k < uncovered_idx.size(); ++k) {
                            set<int> next_s;
                            set_intersection(cand_v.begin(), cand_v.end(),
                                             filtered_sets[uncovered_idx[k]].begin(), filtered_sets[uncovered_idx[k]].end(),
                                             inserter(next_s, next_s.begin()));
                            cand_v = next_s;
                            if (cand_v.empty()) break;
                        }
                        int v_limit = 0;
                        for (int v : cand_v) {
                            if (++v_limit > 50) break;
                            if (v != u) {
                                if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                            }
                        }
                    }
                }
            }
        }
        else if (mode == "12") {
            // 条件: dist_old < L である葉が2つ以上あったら無理
            vector<int> too_close;
            for (int l : leaves) 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 : leaves) if (dist_old[l] > L || dist_old[l] == INF) potential_us.push_back(l);
                if (potential_us.size() > 50) potential_us.resize(50);
                
                // 距離整合の葉も少し試す
                int cnt = 0;
                for (int l : leaves) {
                    if (dist_old[l] == L) {
                        potential_us.push_back(l);
                        if (++cnt >= 10) break;
                    }
                }
            }
            
            for (int u : potential_us) {
                // uを葉から除外した状況で、v (deg 2) が他のすべての葉に対して適切か確認
                // needed: v によってカバーされるべき葉 (dist_old > L or INF)
                vector<int> needed;
                for (int l : leaves) if (l != u && (dist_old[l] > L || dist_old[l] == INF)) needed.push_back(l);
                
                if (needed.empty()) {
                    // v は他の全ての葉から距離 L 以上離れていれば良い
                    int v_tries = 0;
                    for (int v = 1; v <= N; ++v) {
                        if (deg[v] == 2) {
                            // dist_to_leaf[v] は u も含む距離なので、u が近い分には許容される
                            // dist_to_leaf[v] >= L なら安全
                            // dist_to_leaf[v] < L の場合、その近さが u によるものならOK
                            if (dist_to_leaf[v] >= L) {
                                if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                                if (++v_tries > 50) break;
                            } else {
                                // 近い葉が u だけか確認
                                int d_uv = get_single_dist(u, v);
                                if (d_uv == dist_to_leaf[v]) {
                                    // 可能性あり
                                    if (check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                                    if (++v_tries > 50) break;
                                }
                            }
                        }
                    }
                } else {
                    // needed の共通部分を探す
                    int l0 = needed[0];
                    set<int> cands;
                    // BFS from l0
                    queue<pair<int,int>> q; q.push({l0, 0});
                    set<int> vis; vis.insert(l0);
                    while(!q.empty()){
                        auto [c, d] = q.front(); q.pop();
                        if(d == L){
                            if(deg[c] == 2) cands.insert(c);
                            continue;
                        }
                        if(d < L){
                            for(int nxt : adj[c]){
                                if(vis.find(nxt) == vis.end()){
                                    vis.insert(nxt);
                                    q.push({nxt, d+1});
                                }
                            }
                        }
                    }
                    
                    int v_tries = 0;
                    for(int v : cands) {
                        if(v == u) continue;
                        if(check_final(u, v, X, L)) { cout << "Yes" << endl; return 0; }
                        if(++v_tries > 50) 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) continue;
            
            for(int l : leaves) {
                if(dist_old[l] == L - 1) {
                    if(check_final(iso, l, 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) continue;
            
            bool ok = true;
            for(int l : leaves) if(dist_old[l] != 1) { ok = false; break; }
            if(ok) {
                int tries = 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(++tries > 10) break;
                    }
                }
            }
        }
    }
    
    cout << "No" << endl;
    return 0;
}