题意：

n点m边无向图，无自环，无重边
给定的图可以断开连接
下面我们有一个定义：让v1和v2为两个不连通的顶点非空子集
函数f(v1, v2)为真当且仅当下面所有情况否满足：
1. 顶点集v1中的两点无边连接
2.顶点集v2中的两点无边连接
3.对任意在v1中的点和v2中的点，两点间有一条边

创造三个顶点集v1，v2，v3满足如下条件
1.所有顶点集不空
2.每个顶点只能在一个顶点集中
3.f(v1, v2) f(v2, v3) f(v3, v4)都为真
有可能创造这个顶点集吗，如果可能，请打印每个顶点的匹配顶点集

简而言之：就是创建一个三分图。

 

思路：

存边的时候，注意下可能输入的左点大于右点，可以存双边，或者存单边使左点小于右点

存边同时记录下度数。

然后进行集合分配，初始化所有点都是集合1的，从点1开始遍历其邻点，其邻点必须非集合1，先置为集合2

然后再从集合2开始遍历邻点，当某点必须非集合1和集合2，那么就置为集合3，如果三者都非，那么就可以直接退出

当集合分配正常完成后，我们就可以判断下集合之间的边数是否等于总边数。

此外还要判断三个集合是否都非空。

注意最后输出的时候，是按照点的顺序输出点的所在集合（没看清被坑了三四发WA

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 100, M = 3e5 + 100;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
int val[5];
 
void add(int a, int b){
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
 
int main()
{
	scanf("%d%d", &n, &m);
	
	memset(h, -1, sizeof h);
	for(int i = 1; i <= n; i++) color[i] = 1;
	for(int i = 0; i < m; i++){
	    int a, b;
	    scanf("%d%d", &a, &b);
		/*add(a, b);
		add(b, a);*/
        
            if(a < b) add(a, b);
            else add(b, a);
	}
	
	for(int i = 1; i <= n; i++)
		color[i] = 1;
	val[1] = n;
		
	int flag = 0;
	for(int g = 1; g <= n; g++){ 
		for(int i = h[g]; i != -1; i = ne[i]){
			int j = e[i];
			if(color[j] == color[g]){
				if(color[j] == 1) { 
					color[j] = 2;
					val[1]--;
					val[2]++; 
				}
				else if(color[j] == 2) {
					color[j] = 3;
					val[2]--;
					val[3]++;
				} 
				else if(color[j] == 3){
					flag = 1; 
					break;
				}
			}
		}
		if(flag) break;
	} 
	
	if(val[1] * val[2] + val[1] * val[3] + val[2] * val[3] != m) flag = 1;
	
	if(flag || val[1] == 0 || val[2] == 0 || val[3] == 0 || m == 0) puts("-1");
	else {
		for(int i = 1; i <= n; i++) printf("%d%s", color[i], (i == n) ? "\n" : " ");
	}
	
	return 0;
}