1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100000+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 inline int read()23 {24     int x=0,f=1;char ch=getchar();25     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}26     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}27     return x*f;28 }29 int n,m,fa[maxn];30 bool mark[maxn];31 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);};32 int main()33 {34     freopen("input.txt","r",stdin);35     freopen("output.txt","w",stdout);36     n=read();m=read();37     for1(i,n)fa[i]=i;38     for1(i,m)39      {40          int x=find(read()),y=find(read());41          if(x==y)mark[x]=1;else fa[x]=y,mark[y]=mark[x]||mark[y];42      }43     for1(i,n)if(!mark[find(i)]){cout<<"NIE"<<endl;return 0;}44     cout<<"TAK"<<endl;45     return 0;46 }

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100000014 #define maxm 100000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 inline int read()23 {24     int x=0,f=1;char ch=getchar();25     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}26     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}27     return x*f;28 }29 int n,m,s,t,maxflow,tot=1,head[maxn],q[maxm],d[maxn],h[maxn],cur[maxn];30 bool v[maxn];31 struct edge{int from,next,go,v;}e[2*maxm];32 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;}33 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);}34 bool bfs()35 {36     for(int i=s;i<=t;i++)h[i]=-1;37     int l=0,r=1;q[1]=s;h[s]=0;38     while(l<r) 39     {40         int x=q[++l];41         for(int i=head[x];i;i=e[i].next)42          if(e[i].v&&h[e[i].go]==-1)43          {44              h[e[i].go]=h[x]+1;q[++r]=e[i].go;45          }46     }47     return h[t]!=-1;48 }49 int dfs(int x,int f)50 {51     if(x==t) return f;52     int tmp,used=0,i;53     for(int i=head[x];i;i=e[i].next)54      if(e[i].v&&h[e[i].go]==h[x]+1) 55     {56         tmp=dfs(e[i].go,min(e[i].v,f-used));57         e[i].v-=tmp;if(e[i].v)cur[x]=i; 58         e[i^1].v+=tmp;used+=tmp;59         if(used==f)return f;         60     }61     if(!used) h[x]=-1;62     return used; 63 }64 void dinic()65 {66     maxflow=0;67     while(bfs())68     {69         for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf); 70     } 71 }72 int main()73 {74     freopen("input.txt","r",stdin);75     freopen("output.txt","w",stdout);76     n=read();m=read();s=0;t=m+n+n+1;77     for1(i,m)78      {79          int x=read(),y=read();80          insert(s,i,1);81          insert(i,m+x,1);insert(i,m+y,1);82          insert(m+x,m+n+y,1);insert(m+y,m+n+x,1);83      }84     for1(i,n)insert(m+n+i,t,1);85     dinic();86     if(maxflow==n)cout<<"TAK"<<endl;else cout<<"NIE"<<endl;87     return 0;88 }