题目大意：给定一个无向图，要求将一些点红黑染色，使每个点及其相连的点中至少有一个黑色的点和一个红色的点

逗比题ぽい~

对于任意一个大小>=2的连通图，我们只需要搞出这个图的任意一棵生成树，将这棵生成树撸成二分图再染色就一定能满足要求的ぽい~

因此无法满足要求当且仅当存在一个大小为1的联通块ぽい~

并查集即可ぽい~

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 200200 using namespace std; int n,m; namespace Union_Find_Set{ int fa[M],size[M]; int Find(int x) { if(!fa[x]) fa[x]=x,size[x]=1; if(fa[x]==x) return x; return fa[x]=Find(fa[x]); } void Union(int x,int y) { x=Find(x);y=Find(y); if(x==y) return ; fa[x]=y;size[y]+=size[x]; } } int main() { using namespace Union_Find_Set; int i,x,y; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); Union(x,y); } for(i=1;i<=n;i++) if(size[Find(i)]==1) return cout<<"NIE"<