CF1228D.Complete Tripartite

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.

你有一个由 $n$ 个顶点和 $m$ 条边构成的简单无向图。该图不含自环，且任意两个顶点之间至多存在一条边。给定的图可以是非连通的。

我们给出如下定义：

设 $v_1$ 和 $v_2$ 是两个非空且互不相交的顶点子集。当且仅当满足以下全部条件时，$f(v_{1}, v_{2})$ 为真：

1. 顶点集 $v_1$ 中任意两个顶点之间均无边相连；
2. 顶点集 $v_2$ 中任意两个顶点之间均无边相连；
3. 对任意两个顶点 $x$ 和 $y$，若 $x \in v_1$ 且 $y \in v_2$，则 $x$ 与 $y$ 之间必有一条边。

请构造三个顶点集（$v_{1}$、$v_{2}$、$v_{3}$），使其满足以下条件：

1. 所有顶点集均非空；
2. 每个顶点恰好属于且仅属于其中一个顶点集；
3. $f(v_{1}, v_{2})$、$f(v_{2}, v_{3})$、$f(v_{3}, v_{1})$ 均为真。

是否存在满足上述条件的三个顶点集？若存在，请输出每个顶点所属的顶点集编号（即对每个顶点输出其属于 $v_1$、$v_2$ 还是 $v_3$）。

The first line contains two integers $n$ and $m$ ($3 \le n \le 10^{5}$, $0 \le m \le \text{min}(3 \cdot 10^{5}, \frac{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 \le a_{i} \lt b_{i} \le 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.

第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 10^{5}$，$0 \le m \le \text{min}(3 \cdot 10^{5}, \frac{n(n-1)}{2})$），分别表示图中的顶点数和边数。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$（$1 \le a_{i} \lt b_{i} \le n$），表示顶点 $a_{i}$ 与 $b_{i}$ 之间存在一条边。图中不含自环，任意一对顶点之间至多只有一条边。给定的图可能不连通。

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.

如果答案存在，输出 $n$ 个整数；其中第 $i$ 个整数表示第 $i$ 个顶点所属的顶点集编号（编号范围为 $1$ 到 $3$）。否则，输出 $-1$。

若存在多个答案，输出任意一个即可。

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.

In the second example, it's impossible to make such vertex sets.

在第一个例子中，若 $v_{1} = { 1 }$、$v_{2} = { 2, 3 }$、$v_{3} = { 4, 5, 6 }$，则顶点集将满足所有条件。但你也可以以其他方式将顶点分配至顶点集；例如，“2 3 3 1 1 1”等答案同样可被接受。

在第二个例子中，无法构造出满足要求的顶点集。