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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.TreeSet;
public class Solution implements Runnable
	                {
	                    static final long MAX = 464897L;
	                    static class InputReader
	                    {
	                        private InputStream stream;
	                        private byte[] buf = new byte[1024];
	                        private int curChar;
	                        private int numChars;
	                        private SpaceCharFilter filter;
	                        private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	                 
	                        public InputReader(InputStream stream)
	                        {
	                            this.stream = stream;
	                        }
	                        
	                        public int read()
	                        {
	                            if (numChars==-1) 
	                                throw new InputMismatchException();
	                            
	                            if (curChar >= numChars)
	                            {
	                                curChar = 0;
	                                try 
	                                {
	                                    numChars = stream.read(buf);
	                                }
	                                catch (IOException e)
	                                {
	                                    throw new InputMismatchException();
	                                }
	                                
	                                if(numChars <= 0)                
	                                    return -1;
	                            }
	                            return buf[curChar++];
	                        }
	                     
	                        public String nextLine()
	                        {
	                            String str = "";
	                            try
	                            {
	                                str = br.readLine();
	                            }
	                            catch (IOException e)
	                            {
	                                e.printStackTrace();
	                            }
	                            return str;
	                        }
	                        public int nextInt()
	                        {
	                            int c = read();
	                            
	                            while(isSpaceChar(c)) 
	                                c = read();
	                            
	                            int sgn = 1;
	                            
	                            if (c == '-') 
	                            {
	                                sgn = -1;
	                                c = read();
	                            }
	                            
	                            int res = 0;
	                            do 
	                            {
	                                if(c<'0'||c>'9') 
	                                    throw new InputMismatchException();
	                                res *= 10;
	                                res += c - '0';
	                                c = read();
	                            }
	                            while (!isSpaceChar(c)); 
	                            
	                            return res * sgn;
	                        }
	                        
	                        public long nextLong() 
	                        {
	                            int c = read();
	                            while (isSpaceChar(c))
	                                c = read();
	                            int sgn = 1;
	                            if (c == '-') 
	                            {
	                                sgn = -1;
	                                c = read();
	                            }
	                            long res = 0;
	                            
	                            do 
	                            {
	                                if (c < '0' || c > '9')
	                                    throw new InputMismatchException();
	                                res *= 10;
	                                res += c - '0';
	                                c = read();
	                            }
	                            while (!isSpaceChar(c));
	                                return res * sgn;
	                        }
	                        
	                        public double nextDouble() 
	                        {
	                            int c = read();
	                            while (isSpaceChar(c))
	                                c = read();
	                            int sgn = 1;
	                            if (c == '-') 
	                            {
	                                sgn = -1;
	                                c = read();
	                            }
	                            double res = 0;
	                            while (!isSpaceChar(c) && c != '.') 
	                            {
	                                if (c == 'e' || c == 'E')
	                                    return res * Math.pow(10, nextInt());
	                                if (c < '0' || c > '9')
	                                    throw new InputMismatchException();
	                                res *= 10;
	                                res += c - '0';
	                                c = read();
	                            }
	                            if (c == '.') 
	                            {
	                                c = read();
	                                double m = 1;
	                                while (!isSpaceChar(c)) 
	                                {
	                                    if (c == 'e' || c == 'E')
	                                        return res * Math.pow(10, nextInt());
	                                    if (c < '0' || c > '9')
	                                        throw new InputMismatchException();
	                                    m /= 10;
	                                    res += (c - '0') * m;
	                                    c = read();
	                                }
	                            }
	                            return res * sgn;
	                        }
	                        
	                        public String readString() 
	                        {
	                            int c = read();
	                            while (isSpaceChar(c))
	                                c = read();
	                            StringBuilder res = new StringBuilder();
	                            do 
	                            {
	                                res.appendCodePoint(c);
	                                c = read();
	                            } 
	                            while (!isSpaceChar(c));
	                            
	                            return res.toString();
	                        }
	                     
	                        public boolean isSpaceChar(int c) 
	                        {
	                            if (filter != null)
	                                return filter.isSpaceChar(c);
	                            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	                        }
	                     
	                        public String next() 
	                        {
	                            return readString();
	                        }
	                        
	                        public interface SpaceCharFilter 
	                        {
	                            public boolean isSpaceChar(int ch);
	                        }
	                    }
	                     
	                    public static void main(String args[]) throws Exception
	                    {
	                        new Thread(null, new Solution(),"Solution",1<<26).start();
	                    }   
	                    static long gcd(long a, long b) 
	                    { 
	                      if (b == 0) 
	                        return a; 
	                      return gcd(b, a % b);  
	                    } 
	                    static long lcm(long a,long b) {
	                        return (a*b)/gcd(a,b);
	                    }
	                    int maxn = 1000005;
	                    long MOD = 1000000007;
	                    long prime = 29;
	                    ArrayList<Integer> adj[];
	                    HashMap<Integer,Integer> tmap = new HashMap();
	                    int[] val;
	                 
	                	public void run() 
	                    {
	                        InputReader sc = new InputReader(System.in);
	                        PrintWriter w = new PrintWriter(System.out);
	                        int n = sc.nextInt();
	                        int m = sc.nextInt();
	                        adj = new ArrayList[n];
	                        for(int i = 0;i < n;i++) {
	                        	adj[i] = new ArrayList();
	                        }
	                        for(int i = 0;i < m;i++) {
	                        	int a = sc.nextInt()-1;
	                        	int b = sc.nextInt()-1;
	                        	adj[a].add(b);
	                        	adj[b].add(a);
	                        }
	                        for(int i = 0;i < n;i++) {
	                        	TreeSet<Integer> tset = new TreeSet();
	                        	tset.add(1);
	                        	tset.add(2);
	                        	tset.add(3);
	                        	Iterator<Integer> it = adj[i].iterator();
	                        	while(it.hasNext()) {
	                        		int x = it.next();
	                        		if(one.contains(x)) {
	                        			tset.remove(1);
	                        		}
	                        		if(two.contains(x)) {
	                        			tset.remove(2);
	                        		}
	                        		if(three.contains(x)) {
	                        			tset.remove(3);
	                        		}
	                        	}
	                        	if(tset.isEmpty()) {
	                        		w.print("-1");
	                        		w.close();
	                        		System.exit(0);
	                        	}else {
	                        		if(tset.first() == 1) {
	                        			one.add(i);
	                        		}else if(tset.first() == 2) {
	                        			two.add(i);
	                        		}else {
	                        			three.add(i);
	                        		}
	                        	}
	                        }
	                        if(one.size() > 0 && two.size() > 0 && three.size() > 0 && one.size() * two.size() + two.size() * three.size() + three.size() * one.size() == m) {
	                        	for(int i = 0;i < n;i++) {
	                        		if(one.contains(i)) {
	                        			w.print(1 + " ");
	                        		}
	                        		if(two.contains(i)) {
	                        			w.print(2 + " ");
	                        		}
	                        		if(three.contains(i)) {
	                        			w.print(3 + " ");;
	                        		}
	                        	}
	                        }else {
	                        	w.println("-1");
	                        }
	                        w.close();
	                    } 
	                	TreeSet<Integer> one = new TreeSet();
	                	TreeSet<Integer> two = new TreeSet();
	                	TreeSet<Integer> three = new TreeSet();
	                	
	                	boolean res(int a) {
	                		TreeSet<Integer> tset = new TreeSet();
	                		while(a != 0) {
	                			int dig = a % 10;
	                			if(tset.contains(dig)) {
	                				return false;
	                			}
	                			tset.add(dig);
	                			a = a/10;
	                		}
	                		return true;
	                	}
	                	int[] count;
	                	boolean[] color;
	                	boolean[] visited;
	                	int total;
	                	ArrayList<Integer> ans;
	                	void dfs(int a) {
	                		visited[a] = true;
	                		Iterator<Integer> it = adj[a].iterator();
	                		boolean flag = true;
	                		boolean leaf = true;
	                		while(it.hasNext()) {
	                			int x = it.next();
	                			if(!visited[x]) {
	                				leaf = false;
	                				dfs(x);
	                				if(!color[a]) {
	    	                			if(count[x] == 0) {
	    	                				flag = false;
	    	                			}
	    	                		}
	                				count[a] += count[x];
	                			}
	                			               			
	                		}
	                		if(color[a]) {
                				count[a]++;
                			}else {
                				if(flag) {
                					if(total > count[a] && a != 0) {
                						ans.add(a);
                					}
                					else if(total == count[a] && (a == 0)) {
                						ans.add(a);
                					}else if(count[a] == 0 && leaf) {
                						ans.add(a);
                					}
                				}
                			}
	                	}
	                    static long power(long a,long b,long MOD) {
                            long ans = 1;
                            a = a % MOD;
                            while(b != 0) {
                                if(b % 2 == 1) {
                                    ans = (ans * a) % MOD;
                                }
                                a = (a * a) % MOD;
                                b = b/2;
                            }
                            return ans;
                        }
	                    class Equal implements Comparable<Equal>{
	                    	Character a;
	                    	int b;
	                    	public Equal(char a,int b){
	                    		this.a = a;
	                    		this.b = b;
	                    	}
							@Override
							public int compareTo(Equal an) {
								// TODO Auto-generated method stub
								return this.a.compareTo(an.a);
								
							}
	                    }
	                    class Pair implements Comparable<Pair>{
	                        int a;
	                        int b;
	                        int c;
	                        Pair(int a,int b,int c){
	                            this.b = b;
	                            this.a = a;
	                            this.c = c;
	                        }
	                        public boolean equals(Object o) {
	                            Pair p = (Pair)o;
	                            return this.a == p.a && this.b == p.b && this.c == p.c;
	                        }
	                        public int hashCode(){
	                            return Long.hashCode(a)*27 + Long.hashCode(b)*31;
	                        }
	                        public int compareTo(Pair p) {
	                            return Long.compare(this.a,p.a);
	                        }
	                    }
	                    class Pair3 implements Comparable<Pair3>{
	                        int a;
	                        int b;
	                        int c;
	                        Pair3(int a,int b,int c){
	                            this.b = b;
	                            this.a = a;
	                            this.c = c;
	                        }
	                        public boolean equals(Object o) {
	                            Pair3 p = (Pair3)o;
	                            return this.a == p.a && this.b == p.b && this.c == p.c;
	                        }
	                        public int hashCode(){
	                            return Long.hashCode(a)*27 + Long.hashCode(b)*31;
	                        }
	                        public int compareTo(Pair3 p) {
	                            return Long.compare(this.b,p.b);
	                        }
	                    }
	                    class Pair2 implements Comparable<Pair2>{
	                        int a;
	                        int b;
	                        int c;
	                        Pair2(int a,int b,int c){
	                            this.b = b;
	                            this.a = a;
	                            this.c = c;
	                        }
	                        public boolean equals(Object o) {
	                            Pair2 p = (Pair2)o;
	                            return this.a == p.a && this.b == p.b && this.c == p.c;
	                        }
	                        public int hashCode(){
	                            return Long.hashCode(a)*27 + Long.hashCode(b)*31 + Long.hashCode(c)*3;
	                        }
	                        public int compareTo(Pair2 p) {
	                            return Long.compare(p.a,this.a);
	                        }
	                    }
	                }