UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3495. PA2010 Riddle

Statistics 下载数据

Description

有n个城镇被分成了k个郡,有m条连接城镇的无向边。
要求给每个郡选择一个城镇作为首都,满足每条边至少有一个端点是首都。

Input

第一行有三个整数,城镇数n(1<=n<=10^6),边数m(0<=m<=10^6),郡数k(1<=k<=n)。
接下来m行,每行有两个整数ai和bi(ai≠bi),表示有一条无向边连接城镇ai和bi。
接下来k行,第j行以一个整数wj开头,后面是wj个整数,表示第j个郡包含的城镇。

Output

若有解输出TAK,否则输出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

Hint

Source

鸣谢onion_cyc提供翻译