#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[1005],f[1005];
int h[1005];
int hmax[1005];
bool on_diam[1005];
void dfs(int nod,int tata)
{
hmax[nod] = h[nod];
for (auto vecin : g[nod])
{
if (vecin != tata)
{
h[vecin] = 1 + h[nod];
f[nod].push_back(vecin);
dfs(vecin,nod);
hmax[nod] = max(hmax[nod],hmax[vecin]);
}
}
}
bool nod_sussy(int x)
{
for (int i = 1; i <= n; i++)
f[i].clear();
h[x] = 0;
dfs(x,0);
int cnt = 0;
for (auto fiu : f[x])
if (hmax[fiu] >= 3)
cnt++;
if (cnt >= 3)
return true;
return false;
}
bool viz[1005];
int tatar[1005];
void dfss(int nod)
{
viz[nod] = true;
for (auto vecin : g[nod])
if (!viz[vecin])
tatar[vecin] = nod,dfss(vecin);
}
int xx,yy,solopt = 1e9;
int bruh;
vector<int> get_path(int x,int y)
{
memset(viz,0,sizeof(viz));
memset(tatar,0,sizeof(tatar));
dfss(x);
vector<int> diam;
diam.push_back(y);
while (y != x)
{
y = tatar[y];
diam.push_back(y);
}
return diam;
}
int nrop;
int didi;
void hmm(int nod,int tata)
{
if (tata != 0 and g[nod].size() == 1)
{
if (nrop + 2 * didi - 4 < solopt)
{
solopt = nrop + 2 * didi - 4;
xx = nod;
yy = bruh;
}
}
int cntt = 0;
for (auto it : f[nod])
if (hmax[it] - h[it] >= 2)
cntt++;
if (cntt >= 2)
return;
if (cntt == 1)
{
for (auto it : f[nod])
if (hmax[it] - h[it] < 2)
nrop += 2;
for (auto it : f[nod])
if (hmax[it] - h[it] >= 2)
{
didi++;
hmm(it,nod);
didi--;
}
for (auto it : f[nod])
if (hmax[it] - h[it] < 2)
nrop -= 2;
}
else
{
nrop += 2 * (int)f[nod].size() - 2;
for (auto it : f[nod])
{
didi++;
hmm(it,nod);
didi--;
}
nrop -= (2 * (int)f[nod].size() - 2);
}
}
void hoosh(int nod)
{
for (int i = 1; i <= n; i++)
f[i].clear();
h[nod] = 0;
dfs(nod,0);
hmm(nod,0);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
if (m != n - 1)
{
cout << "NO";
return 0;
}
for (int i = 1; i <= n; i++)
{
if (nod_sussy(i))
{
cout << "NO";
return 0;
}
}
if (n == 1 or n == 2)
{
cout << "YES\n";
cout << n << '\n';
for (int i = 1; i <= n; i++)
cout << 1 << ' ';
return 0;
}
cout << "YES\n";
for (int i = 1; i <= n; i++)
{
bruh = i;
if (g[i].size() == 1)
{
hoosh(i);
}
}
vector<int> op;
vector<int> diam = get_path(xx,yy);
for (auto it : diam)
on_diam[it] = true;
op.push_back(diam[1]);
for (int i = 2; i < diam.size() - 1; i++)
{
op.push_back(diam[i]);
for (auto it : g[diam[i]])
if (!on_diam[it])
op.push_back(it),op.push_back(diam[i]);
}
if (op.size() % 2 == 0)
reverse(diam.begin(),diam.end());
op.push_back(diam[1]);
for (int i = 2; i < diam.size() - 1; i++)
{
op.push_back(diam[i]);
for (auto it : g[diam[i]])
if (!on_diam[it])
op.push_back(it),op.push_back(diam[i]);
}
cout << op.size() << '\n';
for (auto it : op)
cout << it << ' ';
return 0;
}
///wtf why does that even work ???
/**
constructie (nush cat de optima dar e o idee)
imi iau diamnetrul
din fiecare punct de pe el pot rasari maxim arbori de inaltime 2 (gen, fiu al diametrului + fiii lui care sunt frunze)
Fie nodurile de pe diametru d[1], d[2], ..., d[k]
Dau initial pe d[2]
Procesul e gen: daca am reusit sa ma asigur ca nu am in candidati toti vecinii lui d[x] in afara de d[x + 1], dau pe d[x + 1]
Daca am dat pe d[x + 1] si tin nodul d[x] alternant, mi se garanteaza inductiv ca de acum aia gen d[i <= x] si chestiile care rasar sunt alternante
Acum, sa zicem ca un sufix din vecinii (nu de pe diametru) ai lui d[x] sunt activi
Il iau pe primul si dau pe el, apoi dau pe 3
Apoi aproximativ repet aceeasi secventa de operatii ca o sa mearga
**/
