P6378 [PA 2010] Riddle

An undirected graph with $n$ vertices and $m$ edges is divided into $k$ parts. Each part contains some vertices. Please choose some key vertices such that each part has **exactly** one key vertex, and each edge has **at least** one endpoint that is a key vertex.

The first line contains three integers $n, m, k$. The next $m$ lines each contain two integers $a, b$, indicating that there is an edge between $a$ and $b$. The next $k$ lines: the first integer is $w$, meaning this part has $w$ vertices; then follow $w$ integers, which are the indices of the vertices in this part.

If it is possible, output `TAK`; otherwise output `NIE`.

#### Constraints For all testdata, it is guaranteed that $1 \le k, w \le n \le 10^6$, $\sum w = n$, $1 \le a, b \le n$, $0 \le m \le 10^6$. Translated by ChatGPT 5