Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 993  Solved: 500

[][][]

Description

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。

任务：

请写一个程序：

1. 读入病毒代码；
2. 判断是否存在一个无限长的安全代码；
3. 将结果输出

Input

 

第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。

Output

你应在在文本文件WIN.OUT的第一行输出一个单词：

1. TAK——假如存在这样的代码；
2. NIE——如果不存在。

Sample Input

3

01

11

00000

Sample Output

NIE

思路

AC自动机+拓扑序列；

代码实现

1 #include
     
       2 const int maxn=3e4+10; 3 int n; 4 char ch[maxn]; 5 int next[maxn][2],fail[maxn],sz=2; 6 bool end[maxn]; 7 void ins(){ 8     int a; 9     scanf("%s",ch);10     for(int i=0,j=0;;i++){11         if(!ch[i]){end[j]=1;break;}12         a=ch[i]-'0';13         if(!next[j][a]) next[j][a]=++sz;14         j=next[j][a];15     }16 }17 int q[maxn],head,tail;18 void build(){19     int a,b;20     head=0,tail=2;21     q[0]=1,q[1]=2;22     while(head