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.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.TreeMap;

public class GraphHash {

	static ArrayList<HashSet<Integer>> adj;
    
	public static void main (String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] ss=br.readLine().trim().split(" ");
		int n=Integer.parseInt(ss[0]);
    	int m=Integer.parseInt(ss[1]);
   		adj=new ArrayList<>();
   		for(int i=0 ; i<=n ; i++){
   		    adj.add(new HashSet<>());
   		}
    	for(int i=0 ; i<m ; i++){
    	    ss=br.readLine().trim().split(" ");
       		int a=Integer.parseInt(ss[0])-1;
       		int b=Integer.parseInt(ss[1])-1;
       		adj.get(a).add(b);
       		adj.get(b).add(a);
    	}
    		int z=helper(n,m);
    		if(z==-1) {
    			System.out.println(-1);
    		}
    	
	}
	
	public static int helper(int n , int m) {
		int[] ans=new int[n];
    	Arrays.fill(ans, -1);
    	for(int g=0 ; g<3 ; g++) {
    		int first=0;
    		for(first=0 ; first<n ; first++) {
    			if(ans[first]==-1) break;
    		}
    		if(first==n) {
    			return -1;
    		}
    		ans[first]=g;
    		for(int j=0 ; j<n ; j++) {
    			if(j!=first && ans[j]==-1 && !adj.get(first).contains(j)) {
    				ans[j]=g;
    			}
    		}
    	}
    	ArrayList<ArrayList<Integer>> groups=new ArrayList<>();
    	for(int i=0 ; i<3 ; i++) {
    		groups.add(new ArrayList<>());
    	}
    	for(int i=0 ; i<ans.length ; i++) {
    		if(ans[i]==-1) return -1;
    		groups.get(ans[i]).add(i);
    	}
    	int edges=0;
    	for(int g1= 0 ;g1<3 ; g1++) {
    		for(int g2=g1+1 ; g2<3 ; g2++) {
    			ArrayList<Integer> l1=groups.get(g1);
    			ArrayList<Integer> l2=groups.get(g2);
    			for(int i=0 ; i<l1.size() ; i++) {
    				for(int j=0 ; j<l2.size() ; j++) {
    					if(adj.get(l1.get(i)).contains(l2.get(j))) {
    						edges++;
    					}else {
    						return -1;
    					}
    				}
    			}
    		}
    	}
    	if(edges!=m) return -1;
    	for(int i:ans) {
    		System.out.print((i+1)+" ");
    	}
    	System.out.println();
		return 0;
	}
	
	
}


