Riddle

Problem Source

PA 2010

Problem Description

An undirected graph with $n$ vertices and $m$ edges is divided into $k$ parts. Each part contains some of the vertices.

Select some "key vertices" such that every part contains exactly one key vertex, and at least one endpoint of every edge 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 an edge between $a$ and $b$.

The next $k$ lines each begin with an integer $w$, the number of vertices in that part, followed by $w$ integers: the vertex indices belonging to that part.

For all test cases, $1 \le k, w \le n \le 10^6$, $\sum w = n$, $1 \le a, b \le n$, and $0 \le m \le 10^6$.

Output Format

If such a selection is possible, output TAK; otherwise output NIE.

Sample Input

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

Sample Output

TAK