/**
 * 競技プログラミング解答コード
 * 言語: C++23
 * 
 * 解法アプローチ:
 * 1. 岩井星人グラフは、頂点数 XY、辺数 XY を持ち、次数1がX個、次数2がX(Y-2)個、次数3がX個です。
 *    また、すべての次数1の頂点から最も近い次数3の頂点までの距離が Y-1 である必要があります。
 *    入力として与えられるグラフは N 頂点 M 辺で、辺を1本追加してこの条件を満たす必要があります。
 *    したがって、追加後のグラフは N 辺を持つため、M = N - 1（森または木）でなければなりません。
 * 
 * 2. 辺を追加することで変化する次数パターンは限られます。
 *    - 次数0(孤立点)がある場合、ない場合で分類できます。
 *    - 次数4以上が存在してはいけません。
 *    - 追加する辺 (u, v) の次数ペアによって、次数1, 2, 3 の頂点数の増減が決まります。
 *    - これにより、最終的な X と Y の候補が決まり、必要な距離 L = Y - 1 が定まります。
 * 
 * 3. 候補となる L に対して、既存の次数3頂点からの距離を確認し、条件を満たさない「悪い葉」や
 *    新たに次数3となるべき「カバー候補」を特定します。
 *    - ケース (1,1): 次数1同士を結ぶ。2つの葉が消える。残りの葉の距離条件を確認。
 *    - ケース (2,2): 次数2同士を結び、新しい次数3を2つ作る。すべての葉が距離 L で次数3に到達できるようにするSet Cover問題として処理。
 *    - ケース (0,1), (0,2): 孤立点の処理。
 * 
 * 4. 候補ペアが見つかった場合、実際に辺を追加してBFSを行い、全条件（次数、距離）を満たすか確認します。
 */

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

using namespace std;

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

// 複数始点からの最短距離を計算 (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);
            }
        }
    }
}

// 指定された頂点対 (u, v) を追加したときに岩井星人グラフになるか判定
bool check_pair(int u, int v, int target_X) {
    // 多重辺チェック
    for (int neighbor : adj[u]) if (neighbor == v) return false;

    // グラフ変更
    deg[u]++; deg[v]++;
    
    // 次数チェック
    if (deg[u] > 3 || deg[v] > 3) { deg[u]--; deg[v]--; return false; }
    
    int n1 = 0, n3 = 0;
    vector<int> deg3_nodes;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 1) n1++;
        else if (deg[i] == 3) {
            n3++;
            deg3_nodes.push_back(i);
        } else if (deg[i] > 3) {
             deg[u]--; deg[v]--; return false;
        }
    }
    
    // Xの一致確認
    if (n1 != n3 || n1 != target_X) { deg[u]--; deg[v]--; return false; }
    if (target_X == 0 || N % target_X != 0) { deg[u]--; deg[v]--; return false; }
    
    int Y = N / target_X;
    if (Y < 2) { deg[u]--; deg[v]--; return false; }
    int L = Y - 1;
    
    // 距離条件の確認 (次数3の頂点群からのBFS)
    static vector<int> d;
    if (d.size() != N + 1) d.resize(N + 1);
    fill(d.begin(), d.end(), -1);
    
    queue<int> q;
    for (int x : deg3_nodes) {
        d[x] = 0;
        q.push(x);
    }
    
    // 辺 (u, v) を考慮したBFS
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        if (d[curr] >= L) continue; // Lより遠くを探索する必要はない（葉までの距離がLかどうかが重要）
        
        auto push = [&](int nxt) {
            if (d[nxt] == -1) {
                d[nxt] = d[curr] + 1;
                q.push(nxt);
            }
        };
        
        for (int nxt : adj[curr]) push(nxt);
        if (curr == u) push(v);
        if (curr == v) push(u);
    }
    
    bool ok = true;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 1) {
            if (d[i] != L) { ok = false; break; }
        }
    }
    
    // 変更を戻す
    deg[u]--; deg[v]--;
    return ok;
}

int main() {
    // 高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> M)) return 0;
    
    // 岩井星人グラフは辺数 N を持つため、追加前は N-1 でなければならない（森）
    if (M != N - 1) { cout << "No" << endl; 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 (any_of(deg.begin(), deg.end(), [](int d){ return d > 3; })) {
        cout << "No" << endl; return 0;
    }
    
    int cnt[5] = {0};
    for (int i = 1; i <= N; ++i) cnt[deg[i]]++;
    
    int c0 = cnt[0];
    int c3 = cnt[3];
    
    // 既存の次数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);
    
    // 候補となる操作（追加する辺のタイプ）と目標X
    vector<pair<string, int>> candidates;
    if (c0 == 0) {
        // 全域をカバー済み。次数1または次数2同士を結ぶ
        if (c3 > 0) candidates.push_back({"11", c3}); // 葉同士を結ぶ (葉が2つ減る, X不変) -> 実は X = C1 - 2 = C3 (元々C1=C3+2)
        candidates.push_back({"22", c3 + 2}); // 次数2同士を結ぶ (Xが2つ増える)
    } else if (c0 == 1) {
        // 孤立点が1つ
        if (c3 > 0) candidates.push_back({"01", c3}); // 孤立点と葉を結ぶ
        candidates.push_back({"02", c3 + 1}); // 孤立点と次数2を結ぶ
    }
    // c0 >= 2 は岩井星人グラフ（連結または特定構造）に不可（サンプル2のようなケースでも成分ごとには成立必要）
    
    for (auto [mode, X] : candidates) {
        if (X <= 0 || N % X != 0) continue;
        int Y = N / X;
        if (Y < 2) continue;
        int L = Y - 1;
        
        vector<int> leaves;
        for (int i = 1; i <= N; ++i) if (deg[i] == 1) leaves.push_back(i);
        
        if (mode == "11") {
            // 現在の葉の中で距離Lを満たさないものをリストアップ
            vector<int> bad;
            for (int l : leaves) {
                if (dist_old[l] != L) bad.push_back(l);
            }
            // 悪い葉が2つなら、それらを結んで解消できるか試す
            if (bad.size() == 2) {
                if (check_pair(bad[0], bad[1], X)) { cout << "Yes" << endl; return 0; }
            } else if (bad.empty() && leaves.size() >= 2) {
                // 全て良いなら、任意の葉ペアで試す（最初のペアで十分）
                if (check_pair(leaves[0], leaves[1], X)) { cout << "Yes" << endl; return 0; }
            }
        }
        else if (mode == "22") {
            // 次数2同士を結んで新しい次数3を2つ作る
            // 既存の次数3から距離L未満の葉があると、距離を伸ばせないので不可
            // 距離Lより遠い葉は、新しい次数3によって距離Lでカバーされなければならない
            vector<set<int>> cover_sets;
            bool possible = true;
            for (int l : leaves) {
                if (dist_old[l] < L) { possible = false; break; }
                if (dist_old[l] == L) continue; // 既存でカバー済み
                
                // 新しいカバー候補を探す (葉から距離Lの地点)
                set<int> s;
                queue<pair<int,int>> q;
                q.push({l, 0});
                set<int> visited; visited.insert(l);
                
                while(!q.empty()){
                    auto [u, d] = q.front(); q.pop();
                    if (d == L) {
                        if (deg[u] == 2) s.insert(u);
                        continue;
                    }
                    for (int v : adj[u]) {
                        if (visited.find(v) == visited.end()) {
                            visited.insert(v);
                            q.push({v, d+1});
                        }
                    }
                }
                if (s.empty()) { possible = false; break; }
                cover_sets.push_back(s);
            }
            
            if (!possible) continue;
            
            if (cover_sets.empty()) {
                // 全ての葉が既存の次数3でカバーされている場合
                // 距離条件を壊さない（葉に近づきすぎない）任意の次数2ペアを探す
                // 葉からの距離が L 以上の次数2頂点が候補
                vector<int> d_leaf(N + 1, INF);
                queue<int> q;
                for(int l : leaves) { d_leaf[l] = 0; q.push(l); }
                while(!q.empty()){
                    int u = q.front(); q.pop();
                    for(int v : adj[u]){
                        if(d_leaf[v] == INF){
                            d_leaf[v] = d_leaf[u] + 1;
                            q.push(v);
                        }
                    }
                }
                vector<int> valid_u;
                for(int i=1; i<=N; ++i) if(deg[i]==2 && d_leaf[i] >= L) valid_u.push_back(i);
                
                // 候補からいくつか試す
                int tries = 0;
                for(size_t i=0; i<valid_u.size() && tries < 50; ++i){
                    for(size_t j=i+1; j<valid_u.size() && tries < 50; ++j){
                        tries++;
                        if(check_pair(valid_u[i], valid_u[j], X)) { cout << "Yes" << endl; return 0; }
                    }
                }
            } else {
                // カバーが必要な葉がある場合
                // 最小の候補集合を持つ葉に着目し、その候補のいずれかを採用する必要がある
                sort(cover_sets.begin(), cover_sets.end(), [](const set<int>& a, const set<int>& b){ return a.size() < b.size(); });
                vector<int> S_min(cover_sets[0].begin(), cover_sets[0].end());
                
                for(int u : S_min) {
                    // u を選んだと仮定し、u でカバーできない残りの集合を特定
                    vector<int> uncovered_idx;
                    for(size_t i=0; i<cover_sets.size(); ++i) {
                        if(cover_sets[i].find(u) == cover_sets[i].end()) uncovered_idx.push_back(i);
                    }
                    
                    if(uncovered_idx.empty()) {
                         // u だけで全てカバーできる場合、v は任意のvalidな頂点で良い
                         // ヒューリスティックに探す
                         for(int v=1; v<=N; ++v){
                             if(deg[v]==2 && v!=u){
                                 if(check_pair(u, v, X)) { cout << "Yes" << endl; return 0; }
                                 if(v > 200 && v % 50 == 0) break; 
                             }
                         }
                    } else {
                        // 残りをカバーできる v を探す (共通部分集合)
                        set<int> intersect = cover_sets[uncovered_idx[0]];
                        for(size_t k=1; k<uncovered_idx.size(); ++k) {
                            set<int> next_s;
                            set_intersection(intersect.begin(), intersect.end(),
                                             cover_sets[uncovered_idx[k]].begin(), cover_sets[uncovered_idx[k]].end(),
                                             inserter(next_s, next_s.begin()));
                            intersect = next_s;
                            if(intersect.empty()) break;
                        }
                        for(int v : intersect) {
                            if(v != u) {
                                if(check_pair(u, v, X)) { cout << "Yes" << endl; return 0; }
                            }
                        }
                    }
                }
            }
        }
        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;
            
            // 接続先の葉 v は、現在の距離が L-1 である必要がある（接続後、孤立点が新しい葉となり距離Lになる）
            vector<int> cands;
            for(int l : leaves) if(dist_old[l] == L-1) cands.push_back(l);
            
            for(int v : cands) {
                // v 以外の葉は距離 L でなければならない
                bool ok = true;
                for(int l : leaves) {
                    if(l != v && dist_old[l] != L) { ok = false; break; }
                }
                if(ok) {
                    if(check_pair(iso, v, X)) { cout << "Yes" << endl; return 0; }
                }
            }
        }
        else if (mode == "02") {
            // 孤立点と次数2を結ぶ (L=1 のケース)
            bool ok = true;
            for(int l : leaves) if(dist_old[l] != 1) { ok = false; break; }
            if(ok) {
                int iso = -1;
                for(int i=1; i<=N; ++i) if(deg[i]==0) { iso = i; break; }
                // 任意の次数2で試す
                for(int i=1; i<=N; ++i) {
                    if(deg[i]==2) {
                        if(check_pair(iso, i, X)) { cout << "Yes" << endl; return 0; }
                        break; 
                    }
                }
            }
        }
    }

    cout << "No" << endl;
    return 0;
}