链接：
题目大意：
构造一个无限长的文本串，使得此串不能被匹配。
正文：
好题。我的一开始的思路是，像 01trie 求最大异或那样跑 trie，然后跳失配指针判断合法。但显然假了。
于是得深度思考题意，“不能被匹配”说明跑 trie 时尽量失配，那么在求出失配指针后被修改的 trie 可以往失配方向走。那么只要在 trie 上 DFS 找出一个没有终止标识的环就好了。
代码：
const int N = 3e4 + 10;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n;
namespace AC
{
int tot;
int t[N][2], g[N][2], fail[N];
bool vis[N], ins[N], f[N];
void Insert(char *s)
{
int p = 0, len = strlen(s);
for (int i = 0; i < len; i++)
{
int ch = s[i] - '0';
if (!t[p][ch]) g[p][ch] = t[p][ch] = ++tot;
p = t[p][ch];
}
f[p] = 1;
}
queue <int> q;
void Build()
{
while (!q.empty()) q.pop();
for (int i = 0; i <= 1; i++)
if (t[0][i]) q.push(t[0][i]);
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = 0; i <= 1; i++)
if(t[u][i])
fail[t[u][i]] = t[fail[u]][i],
f[t[u][i]] |= f[t[fail[u]][i]],
q.push(t[u][i]);
else
t[u][i] = t[fail[u]][i];
}
}
bool ans;
void DFS(int u)
{
if (ins[u]) {ans = 1; return;}
if(vis[u] || f[u]) return;
ins[u] = vis[u] = 1;
DFS(t[u][0]), DFS(t[u][1]);
ins[u] = 0;
}
}
char s[N];
int main()
{
n = Read();
for (int i = 1; i <= n; i++)
scanf ("%s", s), AC::Insert(s);
AC::Build();
AC::DFS(0);
puts (AC::ans? "TAK": "NIE");
return 0;
}