题目描述

有 $n$ 个点， $m$ 条边， $k$ 个非空的点的集合 $A_1 \dots A_k$，满足每个点属于且仅属于一个集合。 现在要在每个集合中选恰好一个点，使得对于每一条边，两个端点中至少有一个被选择。

输入格式

第一行，$n,m,k$。
下面 $m$ 行，每行两个整数，$x,y$。$1 \leq x,y \leq n$，$x \neq y$。
下面 $k$ 行，每行第一个整数 $w$，表示该集合的大小，后面 $w$ 个整数，表示该集合的数。

输出格式

如果可以，第一行输出 TAK，否则输出 NIE 。 如果可以，下面一行，输出 $k$ 个数字，表示每个集合中选择的点。

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

TAK
2 1

3 3 1
1 2
2 3
3 1
3 1 2 3

NIE

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq m \leq 10^6$，$1 \leq k \leq n$。