您有一个简单的无向图,由 $$$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”也将被接受。
在第二个示例中,不可能制作这样的顶点集。