#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

struct node{
    vector<int> vecini;
    int parte;
}graph[100005];

vector<bool> vizitati(100005, false);
int n,m,x,y;

void dfs(int i){
    int k = graph[i].parte;
    vizitati[i]=true;
    //cout<<"inainte primul for"<<endl;
    for(int j=0;j<graph[i].vecini.size();j++)
    {
        if(!vizitati[ graph[i].vecini[j] ])
        {
            if(k==1)
                graph[graph[i].vecini[j] ].parte = 2;
            else
                graph[ graph[i].vecini[j] ].parte = 1;
        }
    }
    //cout<<"inainte al doilea for"<<endl;
    for(int j=0;j<graph[i].vecini.size();j++)
    {
        if(!vizitati[graph[i].vecini[j]])
            dfs( graph[i].vecini[j] );
    }
}

bool verif(){
    for(int i=1;i<=n;i++){
        for(int j=0;j<graph[i].vecini.size();j++)
        {
            if(graph[i].parte == graph[ graph[i].vecini[j] ].parte)
                return false;
        }
    }
    return true;
}

int main()
{
    ifstram f("bipartit.in");
    ofstream g("bipartit.out");
    f>>n>>m;
    while(f>>x>>y)
    {
        graph[x].vecini.push_back(y);
        graph[y].vecini.push_back(x);
    }
    //cout<<"citire"<<endl;
    graph[1].parte = 1;
    //cout<<"evaluare graph[1]"<<endl;
    dfs(1);
    //cout<<"dfs"<<endl;
    cout<<verif();
    return 0;
}