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

using namespace std;

ifstream fin("2sat.in");
ofstream fout("2sat.out");

#define NMAX 100

vector<int> a[NMAX];
vector<int> t[NMAX];
stack<int> stiva;
int n, m;

inline int getPositive(int &n, int &i){
    return i+n;
}

inline int getNegative(int &n, int &i){
    return 2*n-i;
}


void transpus(){
    for(int i=0; i<=2*n; i++){
        if(i == n)continue;

        for(int j=0; j<a[i].size(); j++){
            t[a[i][j]].push_back(i);
        }

    }
}


void addNode(int nod, int v){
    nod = getPositive(n, nod);
    v   = getPositive(n, v);

    a[getNegative(n, v)].push_back(nod);
    a[getNegative(n, nod)].push_back(v);
}

void read(){
    fin>>n>>m;

    int x, y;
    for(int i=1; i<=m; i++){
        fin>>x>>y;

        addNode(x, y);
    }
}

bool viz[128];

void setEmptyViz(){
    for(int i=0; i<128; i++)viz[i] = false;
}

void DFS(int nod){
    viz[nod] = true;

    for(int i=0; i<a[nod].size(); i++){
        if(!viz[a[nod][i]])
            DFS(a[nod][i]);
    }

    stiva.push(nod);
}

int c[128];
bool atrib[128];


void DFS_Transpus(int nod, int tt){
    c[nod] = tt;
    atrib[nod] = false;
    atrib[getNegative(n, nod)] = true;

    for(int i=0; i<t[nod].size(); i++){
        if(!c[t[nod][i]])
            DFS_Transpus(t[nod][i], tt);
    }
}

void getHardConex(){
    int tt = 1;
    for(int i=0; i<=n*2; i++){
        if(i == n)continue;

        int x = stiva.top();
        stiva.pop();

        if(!c[x]){
            DFS_Transpus(x, tt);
            tt++;
        }
    }
}


int main(){
    setEmptyViz();

    read();

    for(int i=0; i<=2*n; i++){
        if(i == n)continue;

        if(!viz[i])
            DFS(i);
    }

    transpus();

    getHardConex();

    fout<<1<<'\n';
    return 0;

    for(int i=0; i<2*n; i++){
        if(i == n)continue;

        if(c[getNegative(n, i)] == c[i]){
            fout<<-1<<'\n';
            return 0;
        }
    }

    for(int i=0; i<n; i++){
        fout<<atrib[i]<<' ';
    }
    //fout<<g->n<<' '<<g->m;

    fout<<'\n';


}