Gambling Machine

A gambling machine is built from $n$ integer generators $G_1, G_2, \ldots, G_n$, where $1 \le n \le 1000$. Each generator $G_i$ is tied to a fixed set $S_i \subseteq \{1, 2, \ldots, n\}$. Let $k_i = |S_i|$; a set may be empty, and the sum $k_1 + k_2 + \cdots + k_n$ never exceeds $12000$.

Each time a generator is activated it produces one integer, according to these rules:

• The first time $G_i$ is activated it produces some element of $S_i$.
• On every later activation $G_i$ produces an element of $S_i$ that it has not produced before. You may choose, for each generator, the order in which its elements come out.
• Once every element of $S_i$ has already been produced (in particular when $S_i$ is empty), $G_i$ produces $0$.

The machine always starts by activating $G_1$. After a generator produces a positive integer $r$, the next generator activated is $G_r$. As soon as some generator produces $0$, the machine halts.

The machine is defeated when the halting $0$ is produced by the last generator $G_n$ and, at that moment, every generator has already used up its whole set (every element of every $S_i$ has been produced). The machine is well constructed when there exists at least one run, over all the ordering choices above, that halts on a $0$ without being a defeat.

Decide whether the given machine is well constructed.

The first line contains one integer $n$ ($1 \le n \le 1000$), the number of generators. Each of the next $n$ lines describes one generator: line $i + 1$ contains $k_i$ followed by the $k_i$ elements of $S_i$, given in arbitrary order and separated by single spaces. Every element lies in $\{1, \ldots, n\}$, the elements on one line are distinct, and $k_1 + \cdots + k_n \le 12000$.

Print TAK if the machine is well constructed, and NIE otherwise.