// https://szkopul.edu.pl/problemset/problem/PaOm0b0Z7CvBDSQxwd1ItSP8/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long
constexpr int sizik = 1000 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector
typedef vec<vec<int>> _kra;

namespace two_sat {

#ifndef GARY_LIB
#include <bits/stdc++.h>
#endif

int neg(int v, int n) {
    if (v > n) {
        return v - n;
    } else {
        return v + n;
    }
}

std::vector<int> post;
int visited[sizik];
int visited_curr = 1;

void DFS(int v, const _kra& kra) {
    if (visited[v] == visited_curr) return;
    visited[v] = visited_curr;
    for (const auto& u : kra[v]) {
        DFS(u, kra);
    }
    post.push_back(v);
}

std::vector<std::vector<int>> SSS;
int idx_of_sss[sizik];
void DFS1(int v, const _kra& kra1) {
    if (visited[v] == visited_curr) return;
    visited[v] = visited_curr;
    SSS.back().push_back(v);
    idx_of_sss[v] = (int)SSS.size() - 1;
    for (const auto& u : kra1[v]) {
        DFS1(u, kra1);
    }
}

std::vector<int> topo_order;
void DFS_TOPO(int v, const _kra& kra_sss) {
    if (visited[v] == visited_curr) return;
    visited[v] = visited_curr;
    for (const auto& u : kra_sss[v]) {
        DFS_TOPO(u, kra_sss);
    }
    topo_order.push_back(v);
}

std::vector<bool> two_sat(const std::vector<ar<int, 2>>& cond, int n) {
    _kra kra(2 * n + 3);
    _kra kra1(2 * n + 3);
    for (auto [a, b] : cond) {
        if (a < 0) a = neg(-a, n);
        if (b < 0) b = neg(-b, n);

        kra[neg(a, n)].push_back(b);
        kra[neg(b, n)].push_back(a);

        kra1[b].push_back(neg(a, n));
        kra1[a].push_back(neg(b, n));
    }

    visited_curr++;
    for (int i = 1; i <= 2 * n; i++) {
        if (visited[i] != visited_curr) DFS(i, kra);
    }
    visited_curr++;
    std::reverse(post.begin(), post.end());
    for (const auto& v : post) {
        if (visited[v] != visited_curr) {
            SSS.push_back({});
            DFS1(v, kra1);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (idx_of_sss[i] == idx_of_sss[neg(i, n)]) {
            std::vector<bool> empty_vector;
            return empty_vector;
        }
    }

    _kra SSS_kra(SSS.size());
    for (int v = 1; v <= 2 * n; v++) {
        int from = idx_of_sss[v];
        for (auto u : kra[v]) {
            int to = idx_of_sss[u];
            if (from != to) {
                SSS_kra[from].push_back(to);
            }
        }
    }
    for (auto& vc : SSS_kra) {
        std::sort(vc.begin(), vc.end());
        vc.erase(std::unique(vc.begin(), vc.end()), vc.end());
    }

    visited_curr++;
    for (int i = 0; i < (int)SSS.size(); i++) {
        if (visited[i] != visited_curr) DFS_TOPO(i, SSS_kra);
    }

    std::reverse(topo_order.begin(), topo_order.end());

    std::vector<int> topo_weights(SSS.size());
    for (int i = 0; i < (int)topo_order.size(); i++) {
        topo_weights[topo_order[i]] = i;
    }

    std::vector<bool> ret(n);
    for (int i = 1; i <= n; i++) {
        if (topo_weights[idx_of_sss[i]] < topo_weights[idx_of_sss[neg(i, n)]]) {
            ret[i - 1] = false;
        } else {
            ret[i - 1] = true;
        }
    }
    return ret;
}

}

void solve() {
    using two_sat::neg;

    int n, m;
    std::cin >> n >> m;

    std::vector<ar<int, 2>> cond;

    int N = 2 * n;

    for (int i = 1; i <= 2 * n; i += 2) {
        cond.push_back({i, i + 1});
        cond.push_back({-i, -(i + 1)});
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;

        cond.push_back({-a, -b});
    }

    auto ret = two_sat::two_sat(cond, N);

    if (ret.empty()) {
        std::cout << "NIE\n";
        return;
    }

    for (int i = 0; i < ret.size(); i++) {
        if (ret[i]) {
            std::cout << (i + 1) << '\n';
        }
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}