수수께끼

사악한 마법사 볼드바이트가 용감한 기사 바이터를 자신의 탑에 가두었다. 볼드바이트는 늘 그래왔듯이, 바이터가 자신이 낸 (아직 아무도 풀지 못한) 수수께끼 중 하나를 풀면 풀어 주겠다고 약속했다. 그러나 바이터가 볼드바이트의 애완용 용을 죽이고 볼드바이트마저 거의 죽일 뻔했기 때문에, 볼드바이트는 특별히 어려운 수수께끼를 내기로 했다. 볼드바이트가 바이터에게 낸 수수께끼는 다음과 같다.

바이트랜드는 $k$개의 주(county)로 나누어져 있고, 전체 도시는 모두 $n$개다. 또한 어떤 도시 쌍들은 양방향 도로로 연결되어 있다. 각 주마다 도시 하나를 골라 그 주의 수도로 삼되, 모든 도로에 대해 두 끝점 중 적어도 하나가 수도가 되도록 하고 싶다. 이것이 가능한가?

가엾은 바이터를 도와 이 수수께끼를 풀어 주자.

첫째 줄에 세 정수가 주어진다. 도시의 수 $n$ ($1 \le n \le 10^6$), 도로의 수 $m$ ($0 \le m \le 10^6$), 주의 수 $k$ ($1 \le k \le n$). 도시는 $1$부터 $n$까지 번호가 매겨진다.

다음 $m$개의 줄에는 각각 두 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 주어지며, 이는 도시 $a_i$와 $b_i$를 잇는 도로를 뜻한다. 어떤 두 도시도 두 개 이상의 도로로 연결되지 않는다.

그다음 $k$개의 줄에는 각 주에 대한 설명이 주어진다. $j$번째 줄은 정수 $w_j$ ($1 \le w_j \le n$), 즉 $j$번째 주에 속한 도시의 수로 시작하고, 이어서 그 주에 속한 서로 다른 도시 번호 $w_j$개가 주어진다. 모든 $w_j$의 합은 $n$과 같다.

한 줄을 출력한다. 모든 도로가 적어도 하나의 수도를 끝점으로 갖도록 각 주의 수도를 정할 수 있으면 TAK(폴란드어로 예)를, 그렇지 않으면 NIE(폴란드어로 아니오)를 출력한다.