#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 1e3 + 3;
vector<int> g[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> freq(2);
vector<int> color(n + 1, -1);
function<void(int, bool)> Dfs = [&](int v, bool c) {
color[v] = c;
freq[c]++;
for (int u : g[v]) {
if (color[u] == -1) {
Dfs(u, !c);
}
}
};
Dfs(1, 1);
if (n > 4) {
cout << "NO" << '\n';
} else {
cout << "YES" << '\n';
if (n == 1) {
cout << 1 << '\n' << 1 << '\n';
}
if (n == 2) {
cout << 2 << '\n' << 1 << ' ' << 1 << '\n';
}
if (n == 3) {
cout << 2 << '\n' << 2 << ' ' << 2 << '\n';
}
if (n == 4) {
cout << 4 << '\n' << 2 << ' ' << 2 << ' ' << 3 << ' ' << 3 << '\n';
}
}
return 0;
}
