#include <bits/stdc++.h>
using namespace std;

struct Clause {
    int firstVar;
    int secondVar;
};

struct Vertex {
    int index;
    int lowLink;
    bool onStack;
};

struct TwoSatisfiability {
    int numVars;
    int x;
    vector<Clause> clauses;
    stack<int> st;
    vector<Vertex> vertices;
    vector<vector<int> > adj;

    TwoSatisfiability(int n, int m) :
        numVars(n),
        clauses(m),
        x(0),
        vertices(n * 2, {-1, -1, false}),
        adj(n * 2, vector<int>())
    {
    }

    // bool tarjan(int &x, int i, vector<int> &result) {
    bool tarjan(int i, vector<int> &result) {
        Vertex &v = vertices[i];
        v.index = x;
        v.lowLink = x;
        v.onStack = true;
        st.push(i);
        x++;
        for (int a : adj[i]) {
            Vertex &w = vertices[a];
            if (w.index == -1) {
                if (!tarjan(a, result)) return false;
                v.lowLink = min(v.lowLink, w.lowLink);
            } else if (w.onStack) {
                v.lowLink = min(v.lowLink, w.index);
            }
        }
        // is a SCC root node
        if (v.lowLink == v.index) {
            for (;;) {
                int i = st.top();
                int iv = inv(i);
                if (vertices[iv].index == v.index) return false;
                st.pop();
                if (i < numVars) {
                    if (result[i] == -1)
                        result[i] = 1;
                } else {
                    if (result[iv] == -1)
                        result[iv] = 0;
                }
                vertices[i].onStack = false;
                if (vertices[i].index == v.index) {
                    break;
                }
            }
        }
        return true;
    }

    inline int idx(int v) { return (v > 0 ? (v - 1) : (numVars - v - 1)); }
    inline int inv(int i) { return i + ((i < numVars) ? numVars : -numVars); }

    bool isSatisfiable(vector<int>& result) {

        // construct the implication graph        (l1 l2) -> !l1 ->l2 !l2->l1
        for(Clause clause : clauses) {
            adj[idx(-clause.firstVar)].push_back(idx(clause.secondVar));
            adj[idx(-clause.secondVar)].push_back(idx(clause.firstVar));
        }

        // find SCC's of graph
        // int x = 0;
        for (int i = 0; i < vertices.size(); i++) {
            Vertex &v = vertices[i];
            if (v.index == -1)  {
                if (!tarjan(i, result)) return false;
            }
        }

        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    TwoSatisfiability twoSat(n, m);
    for (int i = 0; i < m; ++i) {
        cin >> twoSat.clauses[i].firstVar >> twoSat.clauses[i].secondVar;
    }

    vector<int> result(n, -1);
    if (twoSat.isSatisfiable(result)) {
        cout << "SATISFIABLE" << endl;
        for (int i = 1; i <= n; ++i) {
            if (result[i-1]) {
                cout << i;
            } else {
                cout << -i;
            }
            if (i < n) {
                cout << " ";
            } else {
                cout << endl;
            }
        }
    } else {
        cout << "UNSATISFIABLE" << endl;
    }

    return 0;
}