对一棵树黑白染色一定符合题意。

图一定有生成树。

因此，仅有一个孤立节点的联通块不合题意。

DFS。

#include
     
      using namespace std;int n,m,en,x,y,v[1000001],first[500001],next[1000001],cnt;bool vis[500001];void AddEdge(const int &U,const int &V){	v[++en]=V;	next[en]=first[U];	first[U]=en;}void dfs(int U){	vis[U]=1; ++cnt;	for(int i=first[U];i;i=next[i])	  if(!vis[v[i]])	    dfs(v[i]);}int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=m;++i)	  {	  	scanf("%d%d",&x,&y);	  	AddEdge(x,y);	  	AddEdge(y,x);	  }	for(int i=1;i<=n;++i)	  if(!vis[i])		{	  	  cnt=0;	  	  dfs(i);	  	  if(cnt==1)	  	    {	  	      puts("NIE");	  	      return 0;	  	    }	    }	puts("TAK");	return 0;}