#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

int n;
int m;
vector<int> Graph[100111];
bool TFO[100111];
int depth[100111];
int father[100111];

pair<int,int> marked[100111];

bool vers[100111];
vector< pair<int,int> > ans;

bool DFS(int ver,int dad)
{
    int i,j;

    father[ver] = dad;
    depth[ver] = depth[dad] + 1;

    TFO[ver] = true;

    for (i=0;i<Graph[ver].size();i++)
    {
        if (Graph[ver][i] == dad)
            continue;

        if (TFO[ Graph[ver][i] ])
        {
            if (depth[ Graph[ver][i] ] > depth[ver])
                continue;

            if ( (depth[ver] - depth[ Graph[ver][i] ] + 1) % 2 == 0 )
            {
                printf("Yes\n");
                printf("%d %d\n",depth[ver] - depth[ Graph[ver][i] ] + 1);

                ans.clear();

                ans.push_back(make_pair(Graph[ver][i], ver));
                vers[ver] = true;
                vers[ Graph[ver][i] ] = true;

                int cur = ver;
                while(cur != Graph[ver][i])
                {
                    ans.push_back(make_pair(cur,father[cur]));
                    vers[cur] = true;
                    vers[ father[cur] ] = true;
                    cur = father[cur];
                }

                bool isf = true;
                for (j=1;j<=n;j++)
                {
                    if (!vers[j])
                        continue;

                    if (isf)
                    {
                        printf("%d",j);
                        isf = false;
                    }
                    else
                        printf(" %d",j);
                }
                printf("\n");

                for (j=0;j<ans.size();j++)
                {
                    printf("%d %d\n",ans[j].first,ans[j].second);
                }

                return true;
            }
            else
            {
                int cur = ver;
                bool foundit = false;
                pair<int,int> other;

                while(cur != Graph[ver][i])
                {
                    if (marked[cur] != make_pair(-1,-1))
                    {
                        other = marked[cur];
                        marked[cur] = make_pair(-2,-2);
                        foundit = true;
                    }
                    else
                    {
                        marked[cur] = make_pair(ver, Graph[ver][i]);
                    }

                    cur = father[cur];
                }

                if (foundit)
                {
                    ans.clear();

                    ans.push_back(make_pair(Graph[ver][i], ver));
                    vers[ver] = true;
                    vers[ Graph[ver][i] ] = true;

                    cur = ver;
                    while(cur != Graph[ver][i])
                    {
                        if (marked[cur] != make_pair(-2,-2))
                        {
                            ans.push_back(make_pair(cur, father[cur]));
                            vers[cur] = true;
                            vers[ father[cur] ] = true;
                        }

                        cur = father[cur];
                    }

                    ans.push_back(make_pair(other.first,other.second));
                    vers[other.first] = true;
                    vers[other.second] = true;

                    cur = other.first;
                    while(cur != other.second)
                    {
                        if (marked[cur] != make_pair(-2, -2))
                        {
                            ans.push_back(make_pair(cur, father[cur]));
                            vers[cur] = true;
                            vers[ father[cur] ] = true;
                        }

                        cur = father[cur];
                    }

                    printf("Yes\n");
                    printf("%d %d\n",(int)ans.size(),(int)ans.size());

                    bool isf = true;
                    for (j=1;j<=n;j++)
                    {
                        if (!vers[j])
                            continue;

                        if (isf)
                        {
                            printf("%d",j);
                            isf = false;
                        }
                        else
                            printf(" %d",j);
                    }
                    printf("\n");

                    for (j=0;j<ans.size();j++)
                    {
                        printf("%d %d\n",ans[j].first,ans[j].second);
                    }

                    return true;
                }
            }
        }
        else
        {
            if (DFS(Graph[ver][i], ver))
                return true;
        }
    }

    return false;
}

int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);

    int i,j;

    scanf("%d %d",&n,&m);

    for (i=1;i<=n;i++)
    {
        marked[i] = make_pair(-1,-1);
    }

    for (i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    if (!DFS(1,0))
        printf("No\n");

    return 0;
}