Complete Tripartite

You are given a simple undirected graph with $n$ vertices and $m$ edges. The graph has no self-loops, and there is at most one edge between any pair of vertices. The graph may be disconnected.

For two nonempty, disjoint vertex sets $v_1$ and $v_2$, define $f(v_1, v_2)$ as true if and only if all of the following hold:

1. No edge has both endpoints in $v_1$.
2. No edge has both endpoints in $v_2$.
3. For every vertex $x$ in $v_1$ and every vertex $y$ in $v_2$, there is an edge between $x$ and $y$.

Create three vertex sets $v_1$, $v_2$, $v_3$ that satisfy the following:

1. All three sets are nonempty.
2. Each vertex belongs to exactly one of the sets.
3. $f(v_1, v_2)$, $f(v_2, v_3)$, and $f(v_3, v_1)$ are all true.

Determine whether such sets exist. If they do, print the set number of each vertex.

The first line contains two integers $n$ and $m$ ($3 \le n \le 10^{5}$, $0 \le m \le \min(3 \cdot 10^{5}, \frac{n(n-1)}{2})$), the number of vertices and edges. Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$), meaning there is an edge between $a_i$ and $b_i$. The graph has no self-loops, and there is at most one edge between any pair of vertices.

If a valid assignment exists, print $n$ integers. The $i$-th integer is the set number (from 1 to 3) of vertex $i$. Otherwise, print -1. If there are multiple answers, print any of them.

In the first example, $v_1 = \{1\}$, $v_2 = \{2, 3\}$, and $v_3 = \{4, 5, 6\}$ satisfy all conditions. You may assign the vertices differently. Other answers such as "2 3 3 1 1 1" are also accepted.

In the second example, no valid sets can be made.