#include <algorithm> #include <chrono> #include <iostream> #include <numeric> #include <random> #include <utility> #include <vector> using namespace std; using i64 = long long; constexpr int CYCLES = 75; struct DSU { vector<int> fa, siz; DSU(int n) : fa(n) , siz(n, 1) { iota(fa.begin(), fa.end(), 0); } int leader(int u) { while (u != fa[u]) u = fa[u] = fa[fa[u]]; return u; } void merge(int u, int v) { u = leader(u); v = leader(v); if (u == v) return; else if (siz[u] < siz[v]) swap(u, v); siz[u] += siz[v]; fa[v] = u; } bool same(int u, int v) { return leader(u) == leader(v); } }; minstd_rand0 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; vector<pair<int, int>> edges(m); for (auto& [u, v] : edges) cin >> u >> v; if (n <= 15) { vector<int> color(n + 1); auto check = [&]() { bool vis[4] = { false, false, false, false }; for (int i = 1; i <= n; ++i) vis[color[i]] = true; if (!vis[1] || !vis[2] || !vis[3]) return false; DSU uf(n + 1); for (auto [u, v] : edges) { if (color[u] == color[v]) continue; if (uf.same(u, v)) return false; else uf.merge(u, v); } return true; }; bool found = false; auto dfs = [&](auto&& self, int idx = 1) { if (found) return; else if (idx > n) { if (check()) { for (int i = 1; i <= n; ++i) cout << color[i] << ' '; cout << flush; found = true; } return; } for (int i = 1; i <= 3; ++i) { color[idx] = i; self(self, idx + 1); } }; dfs(dfs); return 0; } auto solve = [&]() { vector<int> color(n + 1); DSU uf(n + 1); for (auto [u, v] : edges) { if (uf.same(u, v)) color[u] = color[v] = 1; else uf.merge(u, v); } for (int i = 1; i <= n; ++i) { if (color[i] == 0) color[i] = 2; } if (count(color.begin() + 1, color.end(), 1) == 0) { color[1] = 1; color[2] = 3; } else { auto pos = find(color.begin() + 1, color.end(), 2); if (pos == color.end()) return false; *pos = 3; if (count(color.begin() + 1, color.end(), 2) == 0) return false; } for (int i = 1; i <= n; ++i) cout << color[i] << ' '; cout << flush; return true; }; for (int i = 0; i < CYCLES; ++i) { shuffle(edges.begin(), edges.end(), rng); if (solve()) return 0; } cout << "-1" << endl; return 0; }