#include <iostream>
#include <vector>
#include <queue>

using namespace std;
//by GB Zakeski
int abs (int n)
{
    if (n > 0 ) return n;
    return -1*n;
}

bool SameParty(int A, int B)
{
    if (abs(A-B) != 1) return false;
    if (A%2)
    {
        return A+1 == B;
    }
    else return SameParty(B,A);
}

int SecondPosel (int p)
{
    if (SameParty(p,p+1)) return p+1;
    else return p-1;
}

int getParty (int p)
{
    return (p+1)/2;
}

bool odp[8002];

bool CheckPosel (int toCheck, int &TS, vector <vector <int> > &NL)
{
    int old = toCheck;
    vector <bool> visited(TS);
    visited.at(toCheck) = true;
    queue <int> Q;
    Q.push(toCheck);
    int toConsi,toAdd;
    while (Q.empty() == false)
    {
        toCheck = Q.front();
        visited.at(toCheck) = true;
        Q.pop();
        for (int i=0; i<NL[toCheck].size(); ++i)
        {
            toConsi = NL[toCheck][i];
            toAdd = SecondPosel(toConsi);
            if (visited.at(toAdd) == false)
            {
                visited.at(toAdd) = true;
                Q.push(toAdd);
            }
        }
    }

  //  cout << "For " << old << endl;
   // for (int i=1; i!=TS; ++i) cout << visited[i] << " ";
  //  cout << endl;
    if (visited.at(old) && visited.at(SecondPosel(old))) return false;
    for (int i=1; i!=TS; ++i) if (visited.at(i)) odp[i] = true;
    return true;

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i=0; i!=8002; ++i) odp[i] = false;
    int n,m;
    int a,b;
    cin >> n >> m;
    int TS = 2*n + 1;
    vector <vector <int> > NotLike(TS);
    for (int i=0; i!=m; ++i)
    {
        cin >> a >> b;
        NotLike.at(a).push_back(b);
        NotLike.at(b).push_back(a);
    }

    for (int i=1; i!=n+1; ++i)
    {
        if (odp[2*i-1] == false)
        {
            if (odp[2*i] == false)
            {
                if (CheckPosel(2*i-1,TS,NotLike) == false)
                {
                    if (CheckPosel(2*i,TS,NotLike) == false)
                    {
                        cout << "NIE";
                        return 0;
                    }
                }
            }
        }
    }

    for (int i=1; i!=TS; ++i) if (odp[i]) cout << i << "\n";
    return 0;
}