题目大意:给定一个无向图，将它划分为三个点集，要求在一个点集中的点没有边相连，且颜色相同，不同集合中的点互相有边相连。
( ext{Solution:})
我们发现，与一个点之间没有边相连的一定在同一个集合。
因为如果有边相连就已经违反了一个性质。
那么我们可以轻易确定一个集合。剩下的任务就是在剩下的点中确定另外两个集合。
我们遍历剩下没有确定的所有集合，随意找到一个点，将所有与它相连的、未染色的点划分为一个集合。
这样，剩下的点就是另一个集合。
证明：
对于除去已经确定的集合中的点，随意找到的点，它所相连的边，一种是属于已经确定的集合，就是已经染色的，直接跳过；
否则，其它边所连的点一定与它自己在不同集合中。而且，对于一个合法的划分，这是对所有点都满足的性质。
于是，我们随机找的正确性就有了保障。
并且还能证明出这样划分的集合形态唯一：对于一个点所连的所有点，因为我们选择先确定第一个集合，那么显然一个集合的点是确定的。因为与一个点没有边相连的点是确定的。
进一步地，因为我们已经证明随机选点的正确性，那我们随便选一个点，最终造成的结局一定是合法的（如果这个图有解）。因为对于任意个点都满足那个性质。
所以，我们随机选一个点并染色后，只需要一次判断就行了。
证毕。
首先判断每个集合中的点数是不是(0),无解情况之一。其次，枚举每个点对应的每条边，看看所连的点对应的集合是不是满足连满了对应的所有点。以及判断有没有与它相连的同一集合的点。
这题做完了。复杂度(O( ext{min(n,m)}))的亚子。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
int n,m,tot,head[MAXN<<1];
int col[MAXN],c[MAXN],cl[MAXN][4];
struct edge {
int nxt,to;
} e[MAXN<<1];
inline void add(int x,int y) {
e[++tot].to=y;
e[tot].nxt=head[x];
head[x]=tot;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=m; ++i) {
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
col[1]=1;
c[1]++;
for(int i=head[1]; i; i=e[i].nxt) {
int j=e[i].to;
col[j]=2;
}
for(int i=1; i<=n; ++i)if(!col[i])col[i]=1,c[1]++;
int s=2;
for(; s<=n&&col[s]!=2; s++);
for(int i=head[s]; i; i=e[i].nxt) {
int j=e[i].to;
if(col[j]==1)continue;
col[j]=3;
c[3]++;
}
c[2]=n-c[1]-c[3];
if(!c[1]||!c[2]||!c[3])return 0&puts("-1");
for(int x=1; x<=n; ++x) {
for(int i=head[x]; i; i=e[i].nxt) {
int j=e[i].to;
cl[x][col[j]]++;
}
for(int i=1; i<=3; ++i) {
if(col[x]!=i&&cl[x][i]!=c[i]) {
puts("-1");
return 0;
}
if(col[x]==i&&cl[x][i])return 0&puts("-1");
}
}
for(int i=1; i<=n; ++i)cout<<col[i]<<" ";
return 0;
}