Riddle

The evil sorcerer Voldebyte has imprisoned the brave knight Bytter the Bold in his tower. As is his custom, Voldebyte promises to free Bytter once he solves one of his (still unsolved) riddles. Because Bytter managed to kill Voldebyte's pet dragon and nearly killed Voldebyte himself, Voldebyte has chosen an especially hard riddle. Here is the riddle he poses to Bytter:

Byteland is divided into $k$ counties, containing $n$ towns in total. In addition, some pairs of towns are connected by bidirectional roads. I want to choose one town in each county to be its capital so that, for every road, at least one of its two endpoints is a capital. Is this possible?

Help poor Bytter and solve the riddle for him.

The first line contains three integers: $n$ ($1 \le n \le 10^6$), the number of towns; $m$ ($0 \le m \le 10^6$), the number of roads; and $k$ ($1 \le k \le n$), the number of counties. The towns are numbered from $1$ to $n$.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), meaning there is a road between towns $a_i$ and $b_i$. No pair of towns is connected by more than one road.

Each of the next $k$ lines describes one county. The $j$-th of these lines starts with an integer $w_j$ ($1 \le w_j \le n$), the number of towns in county $j$, followed by $w_j$ distinct integers, the numbers of the towns in county $j$. The sum of all $w_j$ equals $n$.

Print a single line. If it is possible to choose the capitals so that every road has at least one capital endpoint, print TAK (which means yes in Polish). Otherwise print NIE (which means no in Polish).