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.*; 
import java.math.*;
import java.util.*;
 
public class Main {
	//static final long MOD = 998244353;
	static final long MOD = 1000000007;
	static boolean[] visited;
    public static void main(String[] args) throws IOException {
        FastScanner sc=new FastScanner();
        int V = sc.nextInt();
        int E = sc.nextInt();
        Node[] graph = new Node[V];
        for (int i = 0; i < V; i++)
        	graph[i] = new Node(i);
        for (int i = 0; i < E; i++) {
        	int a = sc.nextInt()-1;
        	int b = sc.nextInt()-1;
        	graph[a].addChild(graph[b]);
        	graph[b].addChild(graph[a]);
        }
        
        //BFS
        boolean[] visited = new boolean[V];
        int[] color = new int[V];
        color[0] = 1;
        Node[] parents = new Node[V];
        Queue<Node> q = new LinkedList<Node>();
        for (Node child: graph[0].children) {
        	color[child.n] = 2;
        	parents[child.n] = graph[0];
        	parents[0] = child;
        	break;
        }
        visited[0] = true;
        q.add(graph[0]);
        int vis = 0;
        int USECOL = 2;
        
        while (! q.isEmpty()) {
        	Node check = q.remove();
        	vis++;
        	int c = color[check.n];
        	Node anchor = parents[check.n];
        	if (anchor == null) {
        		color[check.n] = 1;
        		break;
        	}
        	USECOL = 3;
        	int c2 = color[anchor.n];
        	for (Node child: check.children) {
        		if (! visited[child.n]) {
        			visited[child.n] = true;
        			if (child.children.contains(anchor)) {
        				color[child.n] = not(c,c2);
        			} else {
        				color[child.n] = c2;
        			}
        			parents[child.n] = check;
        			q.add(child);
        		}
        	}
        }
        //System.out.println(Arrays.toString(color));
        
        int[] cnt = new int[4];
        for (int i = 0; i < V; i++) {
        	cnt[color[i]] += 1;
        }
        //System.out.println(Arrays.toString(cnt));
        if (vis < V || cnt[1] == 0 || cnt[2] == 0 || cnt[3] == 0) {
        	System.out.println(-1);
        	return;
        }
        for (int i = 0; i < V; i++) {
        	for (Node connection: graph[i].children) {
        		if (color[i] == color[connection.n]) {
        			System.out.println(-1);
        			return;
        		}
        	}
        	if (graph[i].children.size() != V-cnt[color[i]]) {
        		System.out.println(-1);
        		return;
        	}
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < V; i++)
        	ans.append(color[i] + " ");
        System.out.println(ans);
    }
    
    public static int not(int c, int c2) {
    	boolean[] n = new boolean[4];
    	n[c] = true;
    	n[c2] = true;
    	for (int i = 1; i <= 3; i++) {
    		if (! n[i])
    			return i;
    	}
    	return 0;
    }
    
    public static long power(long x, long y, long p) { 
        // Initialize result 
        long res = 1;      
         
        // Update x if it is more   
        // than or equal to p 
        x = x % p;  
      
        while (y > 0) 
        { 
            // If y is odd, multiply x 
            // with result 
            if((y & 1)==1) 
                res = (res * x) % p; 
      
            // y must be even now 
            // y = y / 2 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    }
    
    public static int dist(int[] point, int[] point2) {
    	return (int)(Math.pow((point2[1]-point[1]),2)+Math.pow((point2[0]-point[0]),2));
    }
    
    public static long gcd(long a, long b) {
    	if (b == 0)
    		return a;
    	else
    		return gcd(b,a%b);
    }
    
    public static int[][] sort(int[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    int[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<int[]>() {
			  @Override
        	  public int compare(int[] arr1, int[] arr2) {
	        	    if (arr1[0] != arr2[0])
	        	    	return arr1[0]-arr2[0];
	        	    else
	        	    	return arr1[1]-arr2[1];
	         }
		});
		return array;
	}
    
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        }
    }
}
class Node {
	public HashSet<Node> children;
	public int n;
	
	public Node(int n) {
		this.n = n;
		children = new HashSet<Node>();
	}
	
	public void addChild(Node node) {
		children.add(node);
	}
	
	public void removeChild(Node node) {
		children.remove(node);
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		return n;
	}

	@Override
	public boolean equals(Object obj) {
		if (! (obj instanceof Node)) {
			return false;
		} else {
			Node node = (Node) obj;
			return (n == node.n);
		}
	}
}