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.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    void pre() throws Exception{}
    void solve(int TC)throws Exception{
        int n = ni(), m = ni();
        int[][] e = new int[m][];
        for(int i = 0; i< m; i++)e[i] = new int[]{ni()-1, ni()-1};
        int[] set = new int[n];
        for(int i = 0; i< n; i++)set[i] = i;
        int[][] g = makeU(n, e);
        int arg = 0;
        for(int i = 0; i< n; i++)
            if(g[i].length < g[arg].length)arg = i;
        Arrays.sort(g[arg]);
        for(int i = 0; i< n; i++)if(Arrays.binarySearch(g[arg], i) < 0)set[find(set, i)] = find(set, arg);
        for(int x:g[arg]){
            Arrays.sort(g[x]);
            for(int i = 0; i< n; i++)if(Arrays.binarySearch(g[x], i) < 0)set[find(set, i)] = find(set, x);
        }
        int count = 0;
        int[] mp = new int[n];
        Arrays.fill(mp, -1);
        for(int i = 0; i< n; i++)if(find(set, i) == i)mp[i] = ++count;
        boolean valid = true;
        for(int[] i:e)if(find(set, i[0]) == find(set, i[1]))valid = false;
        if(!valid || count != 3)pn(-1);
        else{
            for(int i = 0; i< n; i++)p(mp[find(set, i)]+" ");pn("");
        }
    }
    int find(int[] set, int u){
        return set[u] = (set[u] == u?u:find(set, set[u]));
    }
    int[][] makeU(int n, int[][] edge){
        int[][] g = new int[n][];int[] cnt = new int[n];
        for(int i = 0; i< edge.length; i++){cnt[edge[i][0]]++;cnt[edge[i][1]]++;}
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< edge.length; i++){
            g[edge[i][0]][--cnt[edge[i][0]]] = edge[i][1];
            g[edge[i][1]][--cnt[edge[i][1]]] = edge[i][0];
        }
        return g;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    long IINF = (long)1e18, mod = (long)1e9+7;
    final int INF = (int)1e9, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
    static boolean multipleTC = false, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        if(fileIO){
            in = new FastReader("input.txt");
            out = new PrintWriter("output.txt");
        }else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();
        for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}
 
    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }
 
        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }   
}