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.
// package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

//****Use Integer Wrapper Class for Arrays.sort()****
public class AO3 {
    public static void main(String[] Args) {
        FastReader scan = new FastReader();
        int n = scan.nextInt();
        int m = scan.nextInt();
        Node[] arr = new Node[n + 1];
        for (int i = 0; i < n; i++) {
            arr[i + 1] = new Node();
        }
        int[] ans = new int[n + 1];
        Set<Integer> s1 = new HashSet<>();
        Set<Integer> s2 = new HashSet<>();
        Set<Integer> s3 = new HashSet<>();
        int fi = 0;
        int se = 0;
        if (m == 0) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < m; i++) {
                int x = scan.nextInt();
                int y = scan.nextInt();
                arr[x].neigh.add(y);
                arr[y].neigh.add(x);
                if (i == 0) {
                    s1.add(x);
                    s2.add(y);
                    fi = x;
                    se = y;
                }
            }
            for (int i = 1; i <= n; i++) {
                if (!arr[fi].neigh.contains(i)) {
                    s1.add(i);
                    ans[i] = 1;
                }
            }
            Set<Integer> cn = new HashSet<>();
            for (Integer i : arr[fi].neigh) {
                cn.add(i);
            }
            int flag = 0;
            for (Integer i : s1) {
                if (arr[i].neigh.size() == cn.size()) {
                    for (Integer j : arr[i].neigh) {
                        if (!cn.contains(j)) {
                            flag = 1;
                            break;
                        }
                    }
                } else {
                    flag = 1;
                }
            }
            for (int i = 1; i <= n; i++) {
                if (!arr[se].neigh.contains(i)) {
                    if (s1.contains(i)) {
                        flag = 1;
                    }
                    s2.add(i);
                    ans[i] = 2;
                }
            }
            Set<Integer> cn2 = new HashSet<>();
            for (Integer i : arr[se].neigh) {
                cn2.add(i);
            }
            for (Integer i : s2) {
                if (arr[i].neigh.size() == cn2.size()) {
                    for (Integer j : arr[i].neigh) {
                        if (!cn2.contains(j)) {
                            flag = 1;
                            break;
                        }
                    }
                } else {
                    flag = 1;
                }
            }
            for(int i=1;i<=n;i++){
                if(!s1.contains(i)&&!s2.contains(i)){
                    s3.add(i);
                    ans[i]=3;
                }
            }
            if(s3.size()==0){
                flag=1;
            }
            else{
                Set<Integer> cn3=new HashSet<>();
                for(Integer i:s3){
                    for(Integer j:arr[i].neigh){
                        cn3.add(j);
                    }
                }
                for(Integer i:s3){
                    if(cn3.contains(i)){
                        flag=1;
                    }
                }
            }
            if(flag==1){
                System.out.println(-1);
            }
            else{
                StringBuilder print=new StringBuilder();
                for(int i=1;i<=n;i++){
                    print.append(ans[i]+" ");
                }
                System.out.println(print);
            }
        }
    }

    static class Node {
        Set<Integer> neigh;

        Node() {
            neigh = new HashSet<>();
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            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;
        }
    }

}
