P2444 [POI 2000] Virus

The Binary Virus Review Committee has recently discovered the following pattern: certain specific binary strings are virus code. If a piece of code contains no occurrence of any virus code, we call this code safe. Now that the committee has identified all virus code segments, determine whether there exists an infinitely long safe binary code. Example: For instance, if $\{011, 11, 00000\}$ are virus code segments, then one possible infinitely long safe code is $010101 \ldots$. If $\{01, 11, 000000\}$ are virus code segments, then there does not exist an infinitely long safe code. Given all virus code segments, determine whether an infinitely long safe code exists.

The first line contains an integer $n$, the number of virus code segments. Each of the next $n$ lines contains a nonempty binary string, representing a virus code segment.

If an infinitely long safe code exists, output `TAK`; otherwise, output `NIE`.

$1 \leq n \leq 2000$, and the total length of all virus code segments does not exceed $3 \times 10^4$. Translated by ChatGPT 5