← 返回题目列表

Codeforces · 1228/D

D. 完整三方

中文机器翻译题面 查看原题

您有一个简单的无向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。该图不包含自环,一对顶点之间最多有一条边。给定的图可以断开。

我们来定义一下。

设 $$$v_1$$$ 和 $$$v_2$$$ 是两个不相交的非空顶点子集。当且仅当满足所有条件时,令 $$$f(v_{1}, v_{2})$$$ 为真:

1. 顶点集 $$$v_1$$$ 中不存在具有两个端点的边。
2. 顶点集 $$$v_2$$$ 中不存在具有两个端点的边。
3. 对于每两个顶点 $$$x$$$ 和 $$$y$$$,使得 $$$x$$$ 在 $$$v_1$$$ 中并且 $$$y$$$ 在 $$$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})$$$ 均为 true。

是否可以创建这样的三个顶点集?如果可能,请打印每个顶点的匹配顶点集。

输入

第一行包含两个整数 $$$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}$$$ 和 $$$a_{i}$$$ 之间有一条边$$$b_{i}$$$。该图不包含自环,一对顶点之间最多有一条边。给定的图可以断开。

输出

如果答案存在,则打印 $$$n$$$ 整数。第 $$$i$$$ 个整数表示第 $$$i$$$ 个顶点的顶点集编号(从 $$$1$$$ 到 $$$3$$$)。否则,打印$$$-1$$$。

如果有多个答案,请打印其中一个。

示例

输入 #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

注意

在第一个示例中,如果 $$$v_{1} = \{ 1 \}$$$、$$$v_{2} = \{ 2, 3 \}$$$ 和 $$$v_{3} = \{ 4, 5, 6 \}$$$ 则顶点集将满足所有条件。但是您可以通过不同的方式将顶点分配给顶点集;其他答案如“2 3 3 1 1 1”也将被接受。

在第二个示例中,不可能制作这样的顶点集。