Description

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.

Input Format

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.

Output Format

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

6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5

TAK

Hint

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