#2649. riddle

题目描述

有n个点，m条边，k个非空的点的集合A1..Ak，满足每个点属于且仅属于一个集合。

现在要在每个集合中选恰好一个点，使得对于每一条边，两个端点中至少有一个被选择。

输入格式

第一行，n，m，k。

下面m行，每行两个整数，x, y。1<=x, y<=n, x!=y

下面k行，每行第一个整数w，表示该集合的大小，后面w个整数，表示该集合的数

1<=n<=1000000 1<=m<=1000000 1<=k<=n

输出格式

如果可以，第一行输出TAK，否则输出NIE。

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

样例

样例输入

样例1  

输入  

6 5 2  

1 2  

3 1  

1 4  

5 2  

6 2  

3 3 4 2  

3 1 6 5  

  

输出  

TAK  

2 1  

  

样例2  

输入  

3 3 1  

1 2  

2 3  

3 1  

3 1 2 3  

  

输出  

NIE  

样例输出

数据范围与提示