#include<iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int>susedi[100005];
int obhodeni[100005];
bool found = 0;
int n;
vector<int>v;
int fin=-1, start = -1;
int target = -1;
void dfs(int x, int step, int last)
{
   // cout<<"curr: "<<x<<endl;
    if(found) return;
    obhodeni[x] = step;
    for(int i=0;i<susedi[x].size();i++)
    {
        //cout<<endl<<"sega sym v"<<x<<"sused: "<<susedi[x][i]<<endl;
        if(found) return;
        if(susedi[x][i]==last) continue;

        if(!obhodeni[susedi[x][i]])
        {
           // cout<<"otivam v "<<susedi[x][i]<<endl;
            dfs(susedi[x][i],step+1, x);
           // if(!found)
           // obhodeni[susedi[x][i]] =0;
        }
        else
        {
            if((step - obhodeni[susedi[x][i]])%2==1 )
            {
               // cout<<"ETO: "<<x<<" "<<susedi[x][i]<<endl;
                target = susedi[x][i];
                fin = x; start = susedi[x][i];
                /**for(int i=1; i<=n;i++)
                {
                    cout<<obhodeni[i]<<" "  ;
                }
                cout<<endl;*/
                found =1;
                return;
            }
        }
    }
    if(!found)
    obhodeni[x] =0;
}

void dfs2(int x)
{
    v.push_back(x);
    if(x==start)
    {
        found =1;
        return;
    }
    for(int i=0; i<susedi[x].size();i++)
    {
        if(found) return;
        if(obhodeni[susedi[x][i]]==obhodeni[x]-1)
        {
            dfs2(susedi[x][i]);
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    int m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        susedi[a].push_back(b);
        susedi[b].push_back(a);
    }
    found =0;
    dfs(1,1,-1);
    if(!found)
    {
        cout<<"No\n";
        return 0;
    }
    found = 0;
    dfs2(fin);
    /*for(int i=1;i<=n;i++)
        cout<<obhodeni[i]<<" " ; cout<<endl;
    for(int i=0; i<v.size();i++)
        cout<<v[i]<<" ";cout<<endl;*/
        cout<<"Yes\n";
    cout<<v.size()<<" "<<v.size()<<endl;
    for(int i=0;i<v.size();i++)
        cout<<v[i]<<" " ;cout<<endl;
    for(int i=1;i<v.size();i++)
    {
        cout<<v[i]<<" "<<v[i-1]<<endl;
    }
    cout<<v[v.size()-1]<<" "<<v[0]<<endl;

    return 0;
}