#include <bits/stdc++.h>
#define MOD 200500
using namespace std;
ifstream fin("2sat.in");
ofstream fout("2sat.out");
map<int,int> disc, low, use, c, g,ans;
deque<int> q;
map<int,vector<int>>v, elem, cv;
vector<int>cap, ord;
int cost;
void dfs(int node)
{
    ++cost;
    disc[node]=cost;
    low[node]=cost;
    use[node]=1;
    q.push_back(node);

    for(auto e:v[node])
        if(disc[e]==MOD)
        {
            dfs(e);
            low[node]=min(low[node], low[e]);
        }
        else if(use[e]==1)
            low[node]=min(low[node], low[e]);

    if(disc[node]==low[node])
    {
        cout<<node<<" ";
        cap.push_back(node);// lista componentelor
        while(!q.empty() && q.back()!=node)
        {
            c[q.back()]=node;
            elem[node].push_back(q.back());//componenta new are elementele astea
            use[q.back()]=0;
            q.pop_back();
        }
        c[node]=node;
        elem[node].push_back(node);
        use[node]=0;
        q.pop_back();
    }
}
void topsort()
{
    int x, ok=-1;
    while(!q.empty())
    {
        x=q.front();
        q.pop_front();
        for(auto i:cv[x])//comvecine pt com x
        {
            --g[i];
            if(g[i]==0)
            {
                for(auto j:elem[i])
                {
                    ord.push_back(j);
                    if(ans[j]==0 && j<0)
                    {
                        ans[j]=ok;//!j
                        ans[-j]=-ok;
                    }
                    else
                    {
                        ans[-j]=-ok;//!j
                        ans[j]=ok;
                    }
                }
                q.push_back(i);
            }
        }
    }
}

int n, m, a,b;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>a>>b;
        v[-1*a].push_back(b);
        v[-1*b].push_back(a);
    }

    for(int i=-n;i<=n;++i)
    {
        low[i]=MOD;
        disc[i]=MOD;
    }
cout<<"A";
    for(int i=-n;i<=n;++i)
        if(disc[i]==MOD)
            dfs(i);
            cout<<'\n';

    for(int i=-n;i<=n;++i)
        cout<<c[i]<< " ";

cout<<"AMS";

    for(int i=1;i<=n;++i)
        if(c[i]==c[-1*i])
        {
            cout<<-1;
            return 0;
        }

    for(auto i:cap)//prin componente
        for(auto j:elem[i])//prin elem componentei
            for(auto k:v[j])//care s vecinii
                if(c[k]!=i)
                cv[i].push_back(c[k]);//componenta i are vecin componenta

    for(auto i:cap)
        for(auto j:cv[i])//grad int
            g[j]++;


    q.clear();
    for(auto i:cap)
        if(g[i]==0)
        {
            q.push_back(i);
            for(auto j:elem[i])
            {
                ord.push_back(j);//-1 e 0, 1 e 1
                ans[j]=-1;
                ans[-j]=1;
            }
        }

    topsort();
    cout<<'\n';
    for(auto i:ord)//did it sort nicely?
        cout<<i<<" ";
    return 0;
}