#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

bool f;
int dim;
int wr = 0;
int ex = 0;
bool used[10];
bool bip1 = true;
int parts[10];
vector <int> graph[10];
vector <int>component;
vector <int>podgr[10];
vector <int>podgr2[10];
bool bip = true;
set<int> mas;
set<int>::iterator m;
vector<int> mas2;
vector<vector<int>> massiv;
vector<int> helpMas;
void checking(int top, int num)
{
    parts[top] = num;
    for(int k = 0; k < podgr[top].size(); k++)
        if(parts[podgr[top][k] - 1] == 0)
            checking(podgr[top][k] - 1, 3-num);
        else if(parts[podgr[top][k] - 1] == num )
        {
            bip = false;
        }

}

void withDel()
{
    for(int j = 0; j < 10; j++)
        for(int k = 0; k <= podgr[j].size(); k++)
            if(k!=podgr[j].size() || podgr[j].size()!=0)
                {
                    if(parts[j]==0)
                        {
                            checking(j, 1);
                        }
                    if(bip == true)
                        {
                            ofstream fout;
                            fout.open("output.out");
                            fout << "Yes " << component.size() << endl;
                            int p = 0;
                            for (m = mas.begin(); m!= mas.end(); ++m)
                                {
                                    if(p!=mas.size()-1)
                                        {
                                            fout << *m << " ";
                                            p++;
                                        }
                                    else
                                        fout << *m;
                                }
                            fout.close();
                            wr = 1;
                            bip = false;
                        }
                    if(bip == false)
                    {
                        j = 10;
                        k = podgr[j].size()+1;
                        //bip = true;
                        for(int h = 0; h < 10; h++)
                            cout << parts[h];
                        cout <<  " not bip";
                    }
                }
}

void buildGraph()
{
    for(int j = 0; j < component.size(); j++)
        {
            for(int u = 0; u < graph[component[j] - 1].size(); u++)
                podgr[component[j] - 1].push_back(graph[component[j] - 1][u]);
        }
    for(int x = 0; x < component.size(); x++)
        mas.insert(component[x]);
    for(int x = 0; x < component.size(); x++)
        mas2.push_back(component[x]);
}

void trycheck(int top, int num,vector<int>vec)
{
    /*bool u = true;
    for(int h = 0; h < vec.size(); h++)
        if(top==vec[h] - 1)
            u = false;
    if(u == true)*/
    if(parts[top] == 0)
        parts[top] = num;
    for(int v = 0; v < 10; v++)
        cout << parts[v] << " ";
    //cout << endl;
    //cout << u << endl;
    //cout << vec.size();
    for(int k = 0; k < podgr2[top].size(); k++){
        cout <<" K " << k <<" ";
        if(podgr2[top][k]!=-1 && parts[podgr2[top][k] - 1] == 0  )
        {
            cout << podgr2[top][k] << " ";
            trycheck(podgr2[top][k] - 1, 3-num,vec );
        }
    else if(podgr2[top][k]!=-1 && parts[podgr2[top][k] - 1] == num )
        {
            bip1 = false;
            //k = 10;
            f = true;
            for(int d = 0; d < 10; d++)
                parts[d]=0;
            return;
        }
        if(!bip1)
            return;
    }
        /*{
            bip = false;
            for(int d = 0; d < dim; d++)
                parts[d]=0;
        }*/
}
void secondCheck(vector<int> vec[], vector<int> str)
{
    int dim1;
    /*for(int s = 0; s < 10; s++)
            podgr2[s].clear();*/
    for(int h = 0; h < 10; h++){
        for(int g = 0; g < podgr2[h].size(); g++)
            cout << podgr2[h][g] << " ";
        cout << endl;
    }
    cout <<"function";
    for(int j = 0; j < str.size(); j++)
        cout << str[j];
    for(int j = 0; j < str.size(); j++)
        for(int h = 0; h < 10; h++)
            for(int g = 0; g < vec[h].size(); g++)
        {
            if(podgr2[h].size()!=0){
            if(h == str[j] - 1)
                podgr2[h].clear();
            else
            {
                if(vec[h][g] == str[j])
                    podgr2[h][g] = -1;
            }
            }
        }
            cout <<"function";
            for(int d = 0; d < 10; d++){
                for(int t = 0; t < podgr2[d].size(); t++)
                    cout << podgr2[d][t] << " ";
            cout << endl;}
    /*for(int j = 0; j < 10; j++)
        for(int l = 0; l <= podgr2[j].size(); l++)
            if(l!=podgr2[j].size() || podgr2[j].size()!=0)*/

                //if (parts[j] == 0)
                    trycheck(0,1, str);
                for(int a = 0; a < 10; a++)
                    parts[a] = 0;
                if(bip1 == true)
                        {
                            cout << "TRUE" << endl;
                            mas.clear();
                            cout<< str[0];
                            for(int h = 0; h < component.size(); h++)
                                cout <<component[h] <<" ";
                            for(int n = 0; n < str.size(); n++)
                                for(int h = 0; h < component.size(); h++)
                                    if(component[h]==str[n])
                                        component[h] = 0;
                            for(int h = 0; h < component.size(); h++)
                                if(component[h]!=0)
                                        mas.insert(component[h]);
                            ofstream fout;
                            fout.open("output.out");
                            fout << "No"  << endl;
                            int p = 0;
                            fout << str.size() << ":";
                            for(int j = 0; j < str.size(); j++)
                                {
                                    if(j!=str.size()-1)
                                        fout << str[j] << " ";
                                    else
                                        fout << str[j] << endl;
                            }
                            fout << component.size()-str.size() << ":";
                            for (m = mas.begin(); m!= mas.end(); ++m)
                                {
                                    if(p!=mas.size()-1)
                                        {
                                            fout << *m << " ";
                                            p++;
                                        }
                                    else
                                        fout << *m;
                                }
                            fout.close();
                            ex = 1;
                        }
                /*if(ex==1)
                {
                    j = 10;
                        l = podgr2[j].size()+1;
                }*/
                    if(bip1 == false)
                    {
                        /*j = 10;
                        l = podgr2[j].size()+1;*/
                        bip1 = true;
                        for(int h = 0; h < 10; h++)
                            cout << parts[h];
                        cout <<  " not bip";
                        //break;
                    }
}
void dfs(int top)
{
    component.push_back(top + 1);
    used[top] = true;
    for(int l = 0; l < graph[top].size(); l++)
        if(!used[graph[top][l] - 1]&& graph[top][0]!= - 1 )
            dfs(graph[top][l] - 1);
}

int main()
{
    int aaa;
    ifstream fin;
    fin.open("input.in");
    fin >> dim;
    fin >> aaa;
    int first;
    int second;
    int k = 0;
    for(int i = 0; i < aaa; i++)
    {
        fin >> first;
        fin >> second;
        graph[first - 1].push_back(second);
        graph[second - 1].push_back(first);
        mas.insert(first);
        mas.insert(second);
    }
    for(int i = 0; i < mas.size(); i++)
        if(mas.count(i+1) == 0)
            graph[i].push_back(-1);
    for(int i = 0; i < dim; i++)
    {
        for(int j = 0; j < graph[i].size(); j++)
            cout << graph[i][j] << " ";
        cout << endl;
    }
    fin.close();
    int yes = 0;
    for(int i = 0; i < dim+1; i++)
        used[i] = false;
    for(int i = 0; i < dim; i++)
        if(!used[i])
        {
            //used[i] = true;
            component.clear();
            if(graph[i][0]!= -1)
            {
                if(i == 0)
                {
                    dfs(i);
                    cout << "component" << endl;
                    for(int j = 0; j < component.size(); j++)
                        cout << component[j] << " ";
                    for(int j = 0; j < component.size(); j++)
                        if(component[j] == 1)
                            yes = 1;
                    if(yes == 1)
                    {
                        for(int h = 0; h < dim; h++)
                        {
                            parts[h] = 0;
                        }
                        mas.clear();
                        buildGraph();
                        /*cout << "podgr" << endl;
                        for(int u = 0; u < 10; u++)
                        {
                            for(int y = 0; y < podgr[u].size(); y++)
                                cout << podgr[u][y] << " ";
                            cout << endl;
                        }*/
                        cout << "parts";
                        for(int j = 0; j < 10; j++)
                            cout << parts[j] << " ";
                        withDel();
                        i = dim;
                        bip = true;

                    }
                }
                else
                {
                    dfs(i);
                    cout << "component" << endl;
                    for(int j = 0; j < component.size(); j++)
                        cout << component[j] << endl;
                }
            }
            else
            {
                component.push_back(i+1);
                cout << "component" << endl;
                for(int j = 0; j < component.size(); j++)
                    cout << component[j] << endl;
            }
        }
                        int r = 0;
                        for(int l = (1 << mas2.size()) - 1; l >=0; l--)
                        {
                            for(int u = 0; u < mas2.size(); u++)
                                if(l & (1 << u))
                                 {
                                     if(typeid( mas2[u]) == typeid(int))
                                     cout << "yes";
                                     //cout << mas2[u] << " ";
                                     if(mas2[u]!=1)
                                        helpMas.push_back(mas2[u]);
                                     cout << mas2[u] << " ";
                                }
                                cout << endl;
                                massiv.push_back(helpMas);
                                helpMas.clear();
                                r++;
                                //cout << r<< endl;
                        }
                        if(wr == 0)
                        {
                        cout << "podgr" << endl;
                        for(int u = 0; u < 10; u++)
                        {
                            for(int y = 0; y < podgr[u].size(); y++)
                                cout << podgr[u][y] << " ";
                            cout << endl;
                        }
                        for(int s = 0; s < 10; s++)
                            for(int y = 0; y < podgr[s].size(); y++)
                                podgr2[s].push_back(podgr[s][y]);
                        cout <<"done";
           //вот тут я удалила код)
                        for(int u = 0; u < massiv.size(); u++)
                        {
                            for(int r = 0; r < massiv[u].size(); r++)
                                cout << massiv[u][r] << " ";
                            cout << endl;
                        }
                        cout << "elem" << endl;
                        for(int y = 0; y < massiv[0].size(); y++)
                            cout << massiv[0][y] << " ";
                        cout << endl;
                        for(int m = massiv.size()-1; m >=1; m-=2)
                        {
                            for(int h = 0; h < dim; h++)
                                parts[h] = 0;
                            if(massiv[m].size()!=0){
                                cout << "size" << massiv[m].size() << endl;
                            secondCheck(podgr, massiv[m]);
                            for(int h = 0; h < 10; h++)
                                podgr2[h].clear();
                            cout << "ok";
                            /*for(int s = 0; s < 10; s++)
                                for(int y = 0; y < podgr2[s].size(); y++)
                                    cout << podgr2[s][y];*/
                            for(int s = 0; s < 10; s++)
                                for(int y = 0; y < podgr[s].size(); y++)
                                    podgr2[s].push_back(podgr[s][y]);
                            cout << "ok";
                            for(int s = 0; s < 10; s++)
                                for(int y = 0; y < podgr2[s].size(); y++)
                                    cout << podgr2[s][y];
                            if(ex == 1){
                                //return 0;
                                cout <<"yes";
                            }}
                        }
                        for(int u = 0; u < 10; u++)
                        {
                            for(int r = 0; r < podgr2[u].size(); r++)
                                cout << podgr2[u][r] << " ";
                            cout << endl;
                        }
                        }
    system("pause");
    return 0;
}