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.
/**
 * BaZ :D
 */

import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main
{
    static MyScanner scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007;
    static long INF = 1_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null, null, "BaZ", 1 << 27) {
            public void run() {
                try {
                    solve();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }
    static int color[];
    static ArrayList<Integer> nadj[];
    static ArrayList<Pair> edges;
    static void solve() throws IOException
    {
        //initIo(true);
        initIo(false);
        StringBuilder sb = new StringBuilder();
        int n = ni(), m = ni();
        edges = new ArrayList<>();
        for(int i=0;i<m;++i) {
            int u = ni(), v = ni();
            edges.add(new Pair(u,v));
        }
//        pl("Adjacenecy list");
//        for(int i=1;i<=n;++i) {
//            for(int  e : adj[i]) {
//                p(e);
//            }
//            pl();
//        }
        color = new int[n+1];
        nadj = new ArrayList[n+1];
        for(int i=1;i<=n;++i) {
            nadj[i] = new ArrayList<>();
        }
        color[1] = 1;
        HashSet<Integer> newSet = new HashSet<>();
        for(Pair p : edges) {
            if(p.x==1) {
                newSet.add(p.y);
            }
            else if(p.y==1) {
                newSet.add(p.x);
            }
        }
//        pl("New Set : ");
//        for(int e : newSet) {
//            p(e);
//        }
//        pl();
        for(Pair p : edges) {
            if(newSet.contains(p.x) && newSet.contains(p.y)) {
                nadj[p.x].add(p.y);
                nadj[p.y].add(p.x);
            }
        }
//        pl("New adjacency list: ");
//        for(int e : newSet) {
//            pl("Vertex "+e+" : ");
//            for(int f : nadj[e]) {
//                p(f);
//            }
//            pl();
//        }
        for(int e : newSet) {
            if(color[e]==0) {
                color[e] = 2;
                dfs(e);
            }
        }
        for(int i=1;i<=n;++i) {
            if(color[i]==0) {
                color[i] = 1;
            }
        }
//        pl("Assigned colors : ");
//        for(int i=1;i<=n;++i) {
//            p(color[i]);
//        }
//        pl();
        int cnt[] = new int[4];
        for(int i=1;i<=n;++i) {
            cnt[color[i]]++;
        }
        if(cnt[1]>0 && cnt[2]>0 && cnt[3]>0 && cnt[1]+cnt[2]+cnt[3]==n) {
            int  mat[][] = new int[4][4];
            for(Pair p : edges) {
                mat[color[p.x]][color[p.y]]++;
                mat[color[p.y]][color[p.x]]++;
            }
            if(mat[1][1]==0 && mat[2][2]==0 && mat[3][3]==0 && mat[1][2]==cnt[2]*cnt[1] && mat[2][3]==cnt[2]*cnt[3] && mat[1][3]==cnt[1]*cnt[3]) {
                for(int i=1;i<=n;++i) {
                    p(color[i]);
                }
                pl();
            }
            else {
                pl(-1);
            }
        }
        else {
            pl(-1);
        }
        pw.flush();
        pw.close();
    }
    static void dfs(int v) {
        for(int e : nadj[v]) {
            if(color[e]==0) {
                color[e] = color[v]  == 2 ? 3 : 2;
                dfs(e);
            }
            else if(color[e]!=(color[v] == 2 ?  3 : 2)) {
                pl(-1);
                System.exit(0);
            }
        }
    }
    static class Pair implements Comparable<Pair>
    {
        int x,y;
        Pair(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
        public int compareTo(Pair other)
        {
            if(this.x!=other.x)
                return this.x-other.x;
            return this.y-other.y;
        }
        public String toString()
        {
            return "("+x+","+y+")";
        }
    }
    static void initIo(boolean isFileIO) throws IOException {
        scan = new MyScanner(isFileIO);
        if(isFileIO) {
            pw = new PrintWriter("/Users/amandeep/Desktop/output.txt");
        }
        else {
            pw = new PrintWriter(System.out, true);
        }
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static String ne() throws IOException
    {
        return scan.next();
    }
    static String nel() throws IOException
    {
        return scan.nextLine();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        MyScanner(boolean readingFromFile) throws IOException
        {
            if(readingFromFile) {
                br = new BufferedReader(new FileReader("/Users/amandeep/Desktop/input.txt"));
            }
            else {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }
        String nextLine()throws IOException
        {
            return br.readLine();
        }
        String next() throws IOException
        {
            if(st==null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}