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

using namespace std;

ifstream cin("2sat.in");
ofstream cout("2sat.out");

const int NMAX = 2e5;

int N, M;
vector <int> g[NMAX + 2], t[NMAX + 2];

bool seen[NMAX + 2];
stack <int> st;

int Inv(int x)
{
	if(x < 0)
		return -x + N;

	return x;
}

int Nrm(int x)
{
	if(x < 0)
		return -x;

	return x + N;
}

void dfs1(int node)
{
	seen[node] = true;

	for(auto it : g[node])
		if(!seen[it]) dfs1(it);

	st.push(node);
}	

int kComp;
int comp[NMAX + 2];

void dfs2(int node)
{
	comp[node] = kComp;

	for(auto it : t[node])
		if(comp[it] == 0)
			dfs2(it);
}

bool sol[NMAX + 2];

int main()
{
	cin >> N >> M;

	for(int i = 1; i <= M; i++)
	{
		int x, y; cin >> x >> y;

		g[Inv(x)].push_back(Nrm(y));
		g[Inv(y)].push_back(Nrm(x));
		
		t[Nrm(y)].push_back(Inv(x));
		t[Nrm(x)].push_back(Inv(y));
	}

	for(int i = 1; i <= 2 * N; i++)
		if(!seen[i]) dfs1(i);

	while(!st.empty())
	{
		int node = st.top(); st.pop();
		
		if(comp[node] == 0)
		{
			kComp++;
			dfs2(node);
		}
	}

	for(int i = 1; i <= 2 * N; i++)
		cout << comp[i] << ' ';
	cout << '\n';

	for(int i = 1; i <= N; i++)
		if(comp[i] == comp[i + N])
		{
			cout << -1 << '\n';
			return 0;
		}
		else
			sol[i] = (comp[i + N] > comp[i]);

	for(int i = 1; i <= N; i++)
		cout << sol[i] << ' ';

	return 0;
}