You have a simple undirected graph consisting of n vertices and m edges. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Let's make a definition.

Let v_1 and v_2 be two some nonempty subsets of vertices that do not intersect. Let f(v_{1}, v_{2}) be true if and only if all the conditions are satisfied:

  1. There are no edges with both endpoints in vertex set v_1. 
  2. There are no edges with both endpoints in vertex set v_2. 
  3. For every two vertices x and y such that x is in v_1 and y is in v_2, there is an edge between x and y. 



Create three vertex sets (v_{1}, v_{2}, v_{3}) which satisfy the conditions below;

  1. All vertex sets should not be empty. 
  2. Each vertex should be assigned to only one vertex set. 
  3. f(v_{1}, v_{2}), f(v_{2}, v_{3}), f(v_{3}, v_{1}) are all true. 



Is it possible to create such three vertex sets? If it's possible, print matching vertex set for each vertex.

Input

The first line contains two integers n and m (3 ≤ n ≤ 10^{5}, 0 ≤ m ≤ min(3 ⋅ 10^{5}, (n(n-1))/(2))) — the number of vertices and edges in the graph.

The i-th of the next m lines contains two integers a_{i} and b_{i} (1 ≤ a_{i} < b_{i} ≤ n) — it means there is an edge between a_{i} and b_{i}. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Output

If the answer exists, print n integers. i-th integer means the vertex set number (from 1 to 3) of i-th vertex. Otherwise, print -1.

If there are multiple answers, print any.

Examples

Input


6 11
1 2
1 3
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6


Output


1 2 2 3 3 3 

Input


4 6
1 2
1 3
1 4
2 3
2 4
3 4


Output


-1

Note

In the first example, if v_{1} = \{ 1 \}, v_{2} = \{ 2, 3 \}, and v_{3} = \{ 4, 5, 6 \} then vertex sets will satisfy all conditions. But you can assign vertices to vertex sets in a different way; Other answers like "2 3 3 1 1 1" will be accepted as well.

<image>

In the second example, it's impossible to make such vertex sets.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	public static Scanner cin = new Scanner(System.in);
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	PrintWriter pw = new PrintWriter(System.out);
	StringTokenizer st = null;
//	List<List<Long>> list;
	long MOD = 998244353L;
	static long MAX = (long)1e12;
	String s, t; 
	int n, m;
	int a[];
	boolean vis[];
	boolean isLeaf[];
	boolean flag = true;
	class AC {
		int x, y;
		public AC(int i, int j) {
			x = i;
			y = j;
		}
	};
	List<Integer> vec[];
	int getMin(int x, int y) {
		return x < y ? x : y;
	}
	public void solve() throws Exception {
		n = cin.nextInt();
		m = cin.nextInt();
		vec = new List[n+1];
		a = new int[n+1];
		vis = new boolean[n+1];
		List<AC> list = new ArrayList<>();
		boolean flag =true;
		int x, y, z;
		for (int i = 1; i <= n; i++) {
			vec[i] = new ArrayList<>();
			vis[i] = false;
			a[i] = 0;
		}
		for (int i = 0; i < m; i++) {
			x = cin.nextInt();
			y = cin.nextInt();
			vec[x].add(y);
			vec[y].add(x);
			list.add(new AC(x, y));
		}
		for (int u : vec[1]) {
			vis[u] = true;
		}
		x = 1;
		y = z = 0;
		a[1] = 1;
		for (int i = 2; i <= n; i++) {
			if (!vis[i]) {
				a[i] = 1;
				x++;
			}
			vis[i] = false;
		}
		vis[1] = false;
		if (vec[1].size() == 0) {
			System.out.println(-1);
			return;
		}
		int v = vec[1].get(0);
		for (int u : vec[v]) {
			vis[u] = true;
		}
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				if (a[i] == 0) {
					a[i] = 2;
					y++;
				} else {
					flag = false;
					break;
				}
			}
		}
		if (!flag) {
			System.out.println(-1);
			return;
		}
		x = y = z = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] == 0) {
				a[i] = 3;
			}
			if (a[i] == 1) x++;
			else if (a[i] == 2) y++;
			else z++;
		}
		int e12 = 0, e23 = 0, e13 = 0;
		for (AC ac : list) {
			int v1 = a[ac.x];
			int v2 = a[ac.y];
			if (v1 == v2) {
				System.out.println(-1);
				return;
			}
			if (v1 > v2) {
				int t = v1;
				v1 = v2;
				v2 = t;
			}
			if (v1 == 1 && v2 == 2) {
				e12++;
			} else if (v1 == 2 && v2 == 3) {
				e23++;
			} else {
				e13++;
			}
		}
		if (x == 0 || y == 0 || z == 0|| x*y !=e12 || y*z != e23 || x*z != e13) {
			System.out.println(-1);
		} else {
			StringBuffer sb = new StringBuffer();
			for (int i = 1; i <= n; i++) {
				sb.append(a[i]).append(" ");
			}
			System.out.println(sb.toString());
		}
		
	}
	class GCDOBJ {
		long x, y;
	}
	long gcd(long x, long y) {
		if (x % y == 0) {
			return y;
		}
		return gcd(y, x % y);
	}
	long extended_gcd(long a, long b, GCDOBJ obj) {
		long ret, tmp;
		if (b == 0) {
			obj.x = 1;
			obj.y = 0;
			return a;
		}
		ret = extended_gcd(b, a % b, obj);
		tmp = obj.x;
		obj.x = obj.y;
		obj.y = tmp - a / b * obj.y;
		return ret;
	}
	
	long getRs(long a, long b, long n) {
		GCDOBJ obj = new GCDOBJ();
		long d = extended_gcd(a, n, obj);
		long x0 = obj.x * (b / d) % n;
		if (x0 < 0) {
			x0 += n;
		}
		return x0;
	}
	public static void main(String [] args) {
		Main t = new Main();
//		int tc = cin.nextInt();
		try {
//			while (tc-- > 0)  {
			while (cin.hasNext()) { 
				t.solve();
			}
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		t.pw.close();
	}
	
	
}
