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.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1228D/c2c365eaf8464b0509392f3446fceb5e5d58fe78.png)In the second example, it's impossible to make such vertex sets.