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.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
namespace input {
template <class T>
inline void _R(T& x) {
  cin >> x;
}
template <class T1, class T2>
inline void _R(pair<T1, T2>& x) {
  _R(x.first);
  _R(x.second);
}
template <class T>
inline void _R(vector<T>& x) {
  for (auto& i : x) _R(i);
}
inline void R() {}
template <class T1, class... T2>
inline void R(T1& x, T2&... y) {
  _R(x);
  R(y...);
}
}  // namespace input
using namespace input;
namespace overload_output {
template <class T1, class T2>
inline ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  return out << p.first << ' ' << p.second;
}
template <class T>
inline ostream& operator<<(ostream& out, vector<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, deque<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, forward_list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
}  // namespace overload_output
using namespace overload_output;
namespace output {
template <class T>
inline void _W(const T& x) {
  cout << x;
}
template <class T1, class T2>
inline void _W(const pair<T1, T2>& p) {
  _W(p.first);
  _W(' ');
  _W(p.second);
}
template <class T>
inline void _W(const vector<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const deque<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const forward_list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2, class T3>
inline void _W(const set<T1, T2, T3>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_set<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
inline void W() { cout << '\n'; }
template <class T>
inline void W(const T& x) {
  _W(x);
  W();
}
template <class T1, class... T2>
inline void W(const T1& x, const T2&... y) {
  _W(x);
  _W(' ');
  W(y...);
}
}  // namespace output
using namespace output;
namespace utility {
inline long long pow(long long b, long long p, long long mod) {
  b %= mod;
  long long ans = 1;
  for (; p > 0; p >>= 1) {
    if (p & 1) {
      ans *= b;
      ans %= mod;
    }
    b *= b;
    b %= mod;
  }
  return ans;
}
}  // namespace utility
using namespace utility;
int n, m;
vector<set<int>> g(100007);
vector<long long> hashv;
vector<vector<int>> cc;
int curcc = 0;
bitset<100007> isTrav = 0;
vector<int> color(100007, 0);
inline void no() {
  W(-1);
  exit(0);
}
inline void outputx() {
  for (int i = 1; i <= n; i++) _W(color[i]), _W(" ");
  exit(0);
}
inline void dfs(int node) {
  isTrav[node] = 1;
  cc[curcc].push_back(node);
  for (auto& i : g[node])
    if (!isTrav[i]) dfs(i);
}
inline long long hashx(int node) {
  const long long h = pow(13, 7, 1000000007);
  long long hashed = 0;
  for (auto& i : g[node]) {
    hashed *= h;
    hashed += i;
    hashed %= 1000000007;
  }
  return hashed;
}
int main() {
  int n, m;
  R(n, m);
  for (int i = 0; i < m; i++) {
    int u, v;
    R(u, v);
    g[u].insert(v);
    g[v].insert(u);
  }
  hashv.resize(n + 7);
  for (int i = 1; i <= n; i++) hashv[i] = hashx(i);
  cc.reserve(100007);
  for (int i = 1; i <= n; i++)
    if (!isTrav[i]) {
      cc.push_back(vector<int>());
      dfs(i);
      curcc++;
    }
  if (curcc > 1) no();
  for (int i = 0; i < curcc; i++) {
    for (int j = 1; j <= 3; j++) {
      int n1 = -1;
      for (int k = 0; k < cc[i].size(); k++) {
        if (color[cc[i][k]] == 0) {
          n1 = cc[i][k];
          break;
        }
      }
      if (n1 == -1) break;
      color[n1] = j;
      for (int k = 0; k < cc[i].size(); k++)
        if (color[cc[i][k]] == 0 && g[cc[i][k]].count(n1) == 0) {
          if (g[cc[i][k]].size() != g[n1].size() ||
              hashv[cc[i][k]] != hashv[n1])
            no();
          color[cc[i][k]] = j;
        }
    }
  }
  int cnt[3] = {0, 0, 0};
  for (int i = 1; i <= n; i++) {
    if (color[i] != 1 && color[i] != 2 && color[i] != 3) no();
    cnt[color[i] - 1]++;
  }
  if (cnt[0] == 0 || cnt[1] == 0 || cnt[2] == 0) no();
  for (int i = 1; i <= n; i++) _W(color[i]), _W(" ");
  return 0;
}
static auto _batch_ios = []() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(5);
  return 42;
}();
