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.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

public class Main2 {

    static long mod = 1000000007;
    static FastScanner scanner;

    static List<Integer>[] graph;

    static long result = 0;

    public static void main(String[] args) {
        scanner = new FastScanner();
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        graph = new List[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt() - 1;
            int b = scanner.nextInt() - 1;
            graph[a].add(b);
            graph[b].add(a);
        }

        int[] colors = new int[n];
        dfs(0, colors);

        int[] rank = new int[4];
        for (int i = 0; i < n; i++) {
            if (colors[i] == 0) {
                System.out.println(-1);
                return;
            }
            rank[colors[i]] = graph[i].size();
        }
        if (rank[1] == 0 || rank[2] == 0 || rank[3] == 0) {
            System.out.println(-1);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (rank[colors[i]] != graph[i].size()) {
                System.out.println(-1);
                return;
            }
        }


        System.out.println(IntStream.of(colors).mapToObj(ii -> "" + ii).collect(Collectors.joining(" ")));
    }

    static int[] av = new int[4];

    static void dfs(int cur, int[] colors) {
        if (colors[cur] > 0) return;

        Arrays.fill(av, 0);
        for (int next : graph[cur]) {
            av[colors[next]] = 1;
        }

        int min = 4;
        for (int i = 1; i < 4; i++) if (av[i] == 0) min = i;

        if (min == 4) {
            System.out.println(-1);
            System.exit(0);
        }
        colors[cur] = min;

        for (int next : graph[cur]) {
            dfs(next, colors);
        }
    }

    static class WithIdx implements Comparable<WithIdx>{
        int val, idx;

        public WithIdx(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }

        @Override
        public int compareTo(WithIdx o) {
            return Integer.compare(val, o.val);
        }
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                e.printStackTrace();
                throw new RuntimeException();
            }
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }

        long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) res[i] = nextLong();
            return res;
        }

        String[] nextStringArray(int n) {
            String[] res = new String[n];
            for (int i = 0; i < n; i++) res[i] = nextToken();
            return res;
        }
    }

    static class PrefixSums {
        long[] sums;

        public PrefixSums(long[] sums) {
            this.sums = sums;
        }

        public long sum(int fromInclusive, int toExclusive) {
            if (fromInclusive > toExclusive) throw new IllegalArgumentException("Wrong value");
            return sums[toExclusive] - sums[fromInclusive];
        }

        public static PrefixSums of(int[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }

        public static PrefixSums of(long[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }
    }

    static class ADUtils {
        static void sort(int[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                int a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }

        static void reverse(int[] arr) {
            int last = arr.length / 2;
            for (int i = 0; i < last; i++) {
                int tmp = arr[i];
                arr[i] = arr[arr.length - 1 - i];
                arr[arr.length - 1 - i] = tmp;
            }
        }

        static void sort(long[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                long a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }
    }

    static class MathUtils {
        static long[] FIRST_PRIMES = {
                2,     3,      5,      7,     11,     13,     17,     19,     23,     29,
                31,     37,     41,     43,     47,     53,     59,     61,     67,     71,
                73,     79,     83,     89  ,   97 ,    101,    103,    107,    109,    113,
                127,    131,    137,    139,    149,    151,    157,    163,    167,    173,
                179,    181,    191,    193,    197,    199,    211,    223,    227,    229,
                233,    239,    241,    251,    257,    263,    269,    271,    277,    281,
                283,    293,    307,    311,    313,    317,    331,    337,    347,    349,
                353,    359,    367,    373,    379,    383,    389,    397,    401,    409,
                419,    421,    431,    433,    439,    443,    449,    457,    461,    463,
                467,    479,    487,    491,    499,    503,    509,    521,    523,    541,
                547,    557,    563,    569,    571,    577,    587,    593,    599,    601,
                607,    613,    617,    619,    631,    641,    643,    647,    653,    659,
                661,    673,    677,    683,    691,    701,    709,    719,    727,    733,
                739,    743,    751,    757,    761,    769,    773,    787,    797,    809,
                811,    821,    823,    827,    829,    839,    853,    857,    859,    863,
                877,    881,    883,    887,    907,    911,    919,    929,    937,    941,
                947,    953,    967,    971,    977,    983,    991,    997,   1009,   1013,
                1019,   1021,   1031,   1033,   1039,   1049,   1051};

        static long[] primes(int to) {
            long[] all = new long[to + 1];
            long[] primes = new long[to + 1];
            all[1] = 1;
            int primesLength = 0;
            for (int i = 2; i <= to; i ++) {
                if (all[i] == 0) {
                    primes[primesLength++] = i;
                    all[i] = i;
                }
                for (int j = 0; j < primesLength && i * primes[j] <= to && all[i] >= primes[j]; j++) {
                    all[(int) (i * primes[j])] = primes[j];
                }
            }
            return Arrays.copyOf(primes, primesLength);
        }

        static long modpow(long b, long e, long m) {
            long result = 1;

            while (e > 0) {
                if ((e & 1) == 1) {
                    /* multiply in this bit's contribution while using modulus to keep
                     * result small */
                    result = (result * b) % m;
                }
                b = (b * b) % m;
                e >>= 1;
            }

            return result;
        }

        static long submod(long x, long y, long m) {
            return (x - y + m) % m;
        }

        static public long gcdF(long a, long b) {
            while (b != 0) {
                long na = b;
                long nb = a % b;
                a = na;
                b = nb;
            }
            return a;
        }
    }
}

/*
5
3 2 3 8 8
2 8 5 10 1

 */

