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.*;
public class A
{
      public static void main(String ar[]) throws Exception
      {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            String s1[]=br.readLine().split(" ");
            int n=Integer.parseInt(s1[0]);
            int m=Integer.parseInt(s1[1]);
            
            HashSet<Integer> hs[]=new HashSet[n+1];
            for(int i=1;i<=n;i++)
             hs[i]=new HashSet<Integer>();
            
            int b[][]=new int[m][2];
            for(int i=0;i<m;i++)
            {
                  String s2[]=br.readLine().split(" ");
                  int u=Integer.parseInt(s2[0]);
                  int v=Integer.parseInt(s2[1]);
                  b[i][0]=u;
                  b[i][1]=v;
                  
                  hs[u].add(v);
                  hs[v].add(u);
            }
            
            HashSet<Integer> h1=new HashSet<Integer>();
            HashSet<Integer> h2=new HashSet<Integer>();
            HashSet<Integer> h3=new HashSet<Integer>();
            
            boolean bb=true;
            int v1=1,v2=-1;
            h1.add(1);
            for(int i=2;i<=n;i++)
            {
             if(!hs[v1].contains(i))
              h1.add(i);
             else
              v2=i;
            }
            
            if(v2==-1)
             bb=false;
            // System.out.println(bb);
            for(int i=1;i<=n && bb;i++)
            {
                  if(i!=v2 && !h1.contains(i) && hs[v2].contains(i))
                   h3.add(i);
            }
            
            for(int i=1;i<=n && bb;i++)
             if(!h1.contains(i) && !h3.contains(i))
              h2.add(i);
            
            int n1=h2.size()+h3.size();
            int n2=h1.size()+h3.size();
            int n3=h1.size()+h2.size();
            
            // System.out.println(h1);
            // System.out.println(h2);
            // System.out.println(h3);
            if(h1.size()==0 || h2.size()==0 || h3.size()==0)
             bb=false;
            
            for(int i=1;i<=n && bb;i++)
            {
                  if(h1.contains(i) && hs[i].size()!=n1)
                   bb=false;
                  
                  if(h2.contains(i) && hs[i].size()!=n2)
                   bb=false;
                  
                  if(h3.contains(i) && hs[i].size()!=n3)
                   bb=false;
            }
            
            for(int i=0;i<m && bb;i++)
            {
                int u=b[i][0];
                int v=b[i][1];
                if(h1.contains(u) && h1.contains(v))
                 bb=false;
                if(h2.contains(u) && h2.contains(v))
                 bb=false;
                if(h3.contains(u) && h3.contains(v))
                 bb=false;
            }
            
            if(!bb)
             System.out.println("-1");
            else
            {
                  StringBuffer sb=new StringBuffer();
                  for(int i=1;i<=n;i++)
                  {
                        if(h1.contains(i))
                         sb.append("1 ");
                        else if(h2.contains(i))
                         sb.append("2 ");
                        else
                         sb.append("3 ");
                  }
                  System.out.println(sb);
            }
      }
}