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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeSet;

public final class CF_589_D2_D
{


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}

	static class Composite implements Comparable<Composite>{
		int v;
		int idx;
		public int compareTo(Composite X) {
			if (v!=X.v)
				return v-X.v;
			return idx-X.idx;
		}
		public Composite(int v, int idx) {
			this.v = v;
			this.idx = idx;
		}
		
		
		
	}

	static long mod=1000000007;

	// Global vars
	static BufferedWriter out;
	static InputReader reader;


	static void test() {
		log("testing");

		log("done");

	}

	static int time;
	static int[] visited;
	static int[] target;
	static boolean[][] forbid;
	static ArrayList<Integer>[] friends;
	
	static int[] anc,rank,max,list;

	static void initSet(int x){
		anc[x]=x;
		rank[x]=0;
		max[x]=x;
	}

	static boolean union(int x,int y){
		//log("unioning x:"+x+" y:"+y);
		int xr=find(x);
		int yr=find(y);
		if (xr!=yr){
			if (rank[xr]<rank[yr]){
				anc[xr]=yr;
				max[yr]=Math.max(max[xr],max[yr]);
				//	max[xr]=max[yr];
			} else if (rank[xr]>rank[yr]) {
				anc[yr]=xr;
				max[xr]=Math.max(max[xr],max[yr]);
				//	max[xr]=max[yr];

			} else {
				anc[yr]=xr;
				rank[xr]++;
				max[xr]=Math.max(max[xr],max[yr]);
				//max[xr]=max[yr];
			}
			return true;
		}
		return false;
	}

	static int find(int x){
		if (anc[x]!=x){
			anc[x]=find(anc[x]);
		}
		return anc[x]; 
	}

	static int[] stack;
	
	static void assign(int u,int color) {
		target[u]=color;
		for (int e=0;e<3;e++) {
			if (e!=color)
				forbid[u][e]=true;
			else
				forbid[u][e]=false;
		}
	}
	
	
	static void solve() {
		
		int n=friends.length;
		Composite[] ar=new Composite[n];
		
		for (int i=0;i<n;i++) {
			ar[i]=new Composite(friends[i].size(),i);
			
		}
		Arrays.sort(ar);
		
		target=new int[n];
		visited=new int[n];
		forbid=new boolean[n][3];
		int time=1;
		Arrays.fill(target, -1);
		int rem=n;
		
		
		int color=0;
		int i=0;
		while (i<n && color<3) {
			Composite X=ar[i];
			if (X.v==0) {
				log("error 1");
				output("-1");
				return;
			}
			int u=X.idx;
			if (target[u]==-1) {
				//log("assiging :"+color+" to :"+u);
				assign(u,color);
				//log(u+" "+target[u]);
				rem--;
				time++;
				for (int v:friends[u]) {
					visited[v]=time;
				}
				for (int v=0;v<n;v++) {
					if (visited[v]<time) {
						if (target[v]!=-1 && target[v]!=color) {
							//log("error 2:"+v+" "+target[v]);
							//log("found "+target[v]+" instead of :"+color);
							output("-1");
							return;
						}
						assign(v,color);
					}
				}
				color++;
			}
			i++;
		}
		if (color<3) {
			output("-1");
			return;
		}
		for (int u=0;u<n;u++) {
			if (target[u]==-1) {
				output("-1");
				return;
			}
		}
		for (int u=0;u<n;u++)
			for (int v:friends[u]) {
				if (target[u]==target[v]) {
					output("-1");
					return;
				}
			}
		
		for (int u=0;u<n;u++) {
			System.out.print((target[u]+1)+" ");
		}
		System.out.print("");
		
	}
	
	static void solveBof() {
		
		int n=friends.length;
		Composite[] ar=new Composite[n];
		
		for (int i=0;i<n;i++) {
			ar[i]=new Composite(friends[i].size(),i);
			
		}
		Arrays.sort(ar);
		
		target=new int[n];
		visited=new int[n];
		forbid=new boolean[n][3];
		int time=1;
		Arrays.fill(target, -1);
		int rem=n;
		
		
		// first wave
		int i=0;
		Composite X=ar[i];
		if (X.v==0) {
			output("-1");
			return;
		}
		int u=X.idx;
		assign(u,0);
		time++;
		for (int v:friends[u]) {
			forbid[v][0]=true;
			visited[v]=time;
		}
		for (int v=0;v<n;v++) {
			if (visited[v]<time) {
				rem--;
				assign(v,0);
			}
		}
		// now second wave
		i++;
		int allocated=1;
		loop:while (i<n) {
			X=ar[i];
			u=X.idx;
			time++;
			if (target[u]==0) {
				
				for (int v:friends[u]) {
					if (target[v]==0) {
						output("-1");
						return;
					}
					visited[v]=time;
					forbid[v][0]=true;
				}
				
			} else {
				rem--;
				assign(u,1);
				for (int v:friends[u]) {
					visited[v]=time;
					forbid[v][1]=true;
				}
				for (int v=0;v<n;v++) {
					if (visited[v]<time) {
						// not connected with u
						// so color =1
						if (target[v]==0) {
							output("-1");
							return;
						}
						rem--;
						assign(v,1);
					}
				}
				break loop;
				
			}
			
		}
		// now 3rd wave
		
		
		
	}
	
	static void solveOld() {
		int n=friends.length;
		int root=-1;
		int MAX=300001;
		
		stack=new int[n];
		
		
		for (int u=0;u<n;u++) {
			if (friends[u].size()<MAX) {
				MAX=friends[u].size();
				root=u;
			}
		}
		
		if (MAX==0) {
			output("-1");
			return;
		}
		
		anc=new int[n];
		rank=new int[n];
		max=new int[n];
		
		
		for (int u=0;u<n;u++)
			initSet(u);
		
		// start with root
		target=new int[n];
		Arrays.fill(target, -1);
		target[root]=0;
		forbid[root][1]=true;
		forbid[root][2]=true;
		
		time=1;
		visited=new int[time];
		
		// root is part of the biggest subset
		// 
		
		for (int v:friends[root]) {
			visited[v]=time;
			forbid[v][0]=true;
		}
		
		// now we have biggest subset
		for (int u=0;u<n;u++) {
			if (visited[u]<time) {
				target[u]=0;
				forbid[u][1]=true;
				forbid[u][2]=true;
				
			}
		}
		
		for (int u=0;u<n;u++) {
			if (target[u]==0) {
				for (int v:friends[u]) {
					if (target[v]==0) {
						output("-1");
						return;
					}
					forbid[v][0]=true;
				}
			}
		}
		
		// now, let's look at the other ones...
		
		
		
		
		
		
		
	}
	
	static void process() throws Exception {


		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);

	
		
		int n=reader.readInt();
		int m=reader.readInt();
		
		friends=new ArrayList[n];
		for (int u=0;u<n;u++)
			friends[u]=new ArrayList<Integer>();
		
		for (int i=0;i<m;i++) {
			int u=reader.readInt()-1;
			int v=reader.readInt()-1;
			friends[u].add(v);
			friends[v].add(u);
		}

		solve();
		


		try {
			out.close();
		} catch (Exception e) {
		}

	}

	public static void main(String[] args) throws Exception {
		process();

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}