CF1228D Complete Tripartite
题目描述
给定一个包含 $n$ 个顶点和 $m$ 条边的简单无向图。该图不包含自环，任意一对顶点之间至多有一条边。该图可以是不连通的。
我们定义如下：
设 $v_1$ 和 $v_2$ 是两个不相交的非空顶点集合。若且仅若满足以下所有条件，称 $f(v_1, v_2)$ 成立：
1. 在顶点集合 $v_1$ 内没有两端都在 $v_1$ 的边。
2. 在顶点集合 $v_2$ 内没有两端都在 $v_2$ 的边。
3. 对于任意 $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)$ 都成立。
是否存在这样的划分？如果存在，请输出每个顶点所属的集合编号。
输入格式
第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 10^5$，$0 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2})$），表示图的顶点数和边数。
接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le n$），表示在 $a_i$ 和 $b_i$ 之间有一条边。图中不包含自环，任意一对顶点之间至多有一条边。该图可以是不连通的。
输出格式
如果存在满足条件的划分，输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个顶点所属的集合编号（$1$ 到 $3$ 之一）。如果不存在，输出 $-1$。
如果有多组答案，输出任意一组均可。
说明/提示
在第一个样例中，如果 $v_1 = \{1\}$，$v_2 = \{2, 3\}$，$v_3 = \{4, 5, 6\}$，则所有条件都满足。但你也可以用不同的方式划分顶点集合；例如 “2 3 3 1 1 1” 也是合法答案。
在第二个样例中，不可能划分出满足条件的顶点集合。
由 ChatGPT 4.1 翻译