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.io.PrintWriter;
import java.util.*;

public class d1 extends PrintWriter {

    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    // static Scanner s=new Scanner(System.in);
    d1 () { super(System.out); }
    public static void main(String[] args) throws IOException{
        d1 d1=new d1();d1.main();d1.flush();
    }
    void main() throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        StringBuffer sb1 = new StringBuffer();
        PrintWriter out = new PrintWriter(System.out);
       String[] s1=s();
       int n=i(s1[0]);int m=i(s1[1]);
      ArrayList<Integer>[] adj=new ArrayList[n+1];
      int[] val=new int[n+1];
      Arrays.fill(val,1);
      PriorityQueue<Pair> pq=new PriorityQueue<>(new Comparator<Pair>() {
          @Override
          public int compare(Pair o1, Pair o2) {
              return o1.b-o2.b;
          }
      });
      for(int i=1;i<=n;i++){
          pq.add(new Pair(i,1));
      }
      for(int i=0;i<m;i++){
           String[] s2=s();
           int u=i(s2[0]);int v=i(s2[1]);
           if(adj[u]==null) adj[u]=new ArrayList<>();
           if(adj[v]==null) adj[v]=new ArrayList<>();
           adj[v].add(u);adj[u].add(v);
       }int[] vis=new int[n+1];int flag=0;
       while(!pq.isEmpty()){
          Pair p=pq.poll();
          if(val[p.a]!=p.b) continue;
          vis[p.a]=1;
          if(adj[p.a]==null) continue;
          for(Integer j:adj[p.a]){
              if(vis[j]==1) {
                  if(val[j]==p.b&&val[j]==3){
                      flag=1;break;
                  }continue;
              }
              if(val[j]==p.b&&val[j]==3){
                  flag=1;break;
              }
              if(val[j]==p.b) {val[j]+=1;pq.add(new Pair(j,val[j]));}

          }if(flag==1) break;
      }int[][] ne=new int[n+1][4];
      for(int i=1;i<=n;i++){ if(adj[i]==null) continue;
           for(Integer j:adj[i]){
               ne[i][val[j]]++;
           }
      }
      if(flag==1) System.out.println(-1);
       else {int[] cnt=new int[4];
          for (int i=1;i<=n;i++){ cnt[val[i]]++;sb.append(val[i] + " ");}
          if(cnt[1]==0||cnt[2]==0||cnt[3]==0) System.out.println(-1);
          else{
              for(int i=1;i<=n;i++){
                  if(val[i]==1){
                      if(cnt[2]!=ne[i][2]||cnt[3]!=ne[i][3]){
                          flag=1;break;
                      }
                  }else if(val[i]==2){
                      if(cnt[1]!=ne[i][1]||cnt[3]!=ne[i][3]){
                          flag=1;break;
                      }
                  }else{
                      if(cnt[2]!=ne[i][2]||cnt[1]!=ne[i][1]){
                          flag=1;break;
                      }
                  }
              }if(flag==1) System.out.println(-1);
              else
          System.out.println(sb);
          }
      }
    }

    public void arr(int[] a,int n) throws IOException{
        //        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        String[] s2=s();
        for(int i=0;i<n;i++){
            a[i]=i(s2[i]);
        }
    }
    public void sort(int[] a,int l,int h){
        if(l==h) return;
        int mid=(l+h)/2;

        sort(a,l,mid);
        sort(a,mid+1,h);
        merge(a,l,(l+h)/2,h);
    }
    void merge(int arr[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }


    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static String[] s() throws IOException {
        return s.readLine().trim().split("\\s+");
    }

    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }
}
class Student {
    long  a;int b;int c;
    public Student(int a,int b) {
        this.a=a;this.c=c;this.b=b;
    }
}
class Pair {
    int  a,b,c;
    public Pair(int  a,int b){
        this.a=a;this.b=b;this.c=c;}
}
class Sortbyroll implements Comparator<Student> {

    public int compare(Student a, Student b){
        if(a.b==b.b) return (int)b.a-(int)a.a;
        return   a.b-b.b;}
}

