int ch[100005][2], fail[100005], tot; bool tag[100005];
inlinevoidinsert(char *str, int l){ int x = 0; for (int i = 1; i <= l; i++) { if (!ch[x][str[i] - '0']) { ch[x][str[i] - '0'] = ++tot; } x = ch[x][str[i] - '0']; } tag[x] = 1; }
queue<int> q;
inlinevoidgetfail(){ for (int i = 0; i < 2; i++) if (ch[0][i]) q.push(ch[0][i]); while (!q.empty()) { int x = q.front(); q.pop(); tag[x] |= tag[fail[x]]; for (int i = 0; i < 2; i++) { if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]); else ch[x][i] = ch[fail[x]][i]; } } }
int dfn[30005], low[30005], stk[30005], tme, top; bool vis[30005], flag;
voidtarjan(int x){ dfn[x] = low[x] = ++tme; vis[x] = 1; stk[++top] = x; for (int i = 0; i < 2; i++) { if (tag[ch[x][i]]) continue; int y = ch[x][i]; if (x == y) flag = 1; if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); } elseif (vis[y]) { low[x] = min(low[x], dfn[y]); } } if (dfn[x] == low[x]) { int now = 0, totot = 0; do { now = stk[top--]; vis[now] = 0; totot++; } while (now != x); if (totot > 1) flag = 1; } }
intmain(){ scanf("%d", &n); for (int i = 1; i <= n; i++) { memset(s, 0, sizeof(s)); scanf("%s", s+1); len = strlen(s+1); insert(s, len); } getfail(); flag = 0; tarjan(0); if (flag) puts("TAK"); elseputs("NIE"); return0; }