3495. PA2010 Riddle
#3495. PA2010 Riddle
题目描述
有n个城镇被分成了k个郡，有m条连接城镇的无向边。
要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。
输入格式
第一行有三个整数，城镇数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个郡包含的城镇。
输出格式
若有解输出TAK，否则输出NIE。
样例
样例输入
6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5
样例输出
TAK