Complete Tripartite

题意翻译

有一个 $n$ 个点 $m$ 条边的无向图，每一对顶点中最多有一条边。 设 $v_1,v_2$ 是两个不相交的非空子集，当满足下列条件时，$f(v_1,v_2)$ 的值为真： - $v_1$ 中的点之间不存在边。 - $v_2$ 中的点之间不存在边。 - 对于 $\forall x\in v_1$，$\forall y\in v_2$，$x$ 和 $y$ 之间有边。 问是否存在三个点集 $v_1,v_2,v_3$，使得 $f(v_1,v_2)$，$f(v_2,v_3)$ 和 $f(v_1,v_3)$ 的值均为真。 如果是，输出每一个点所在的点集；否则输出 `-1`。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

6 11
1 2
1 3
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

输出样例 #1

1 2 2 3 3 3 

输入样例 #2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出样例 #2

-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.