PA2010 Riddle

时间限制:30s    【提交】    空间限制:512MB

题目描述

k个国家,几个城市,m条边。
要求每个国家有且仅有一个首都,每条边两端的城市至少要有一个首都。
判断是否有解, 有解输出“TAK”,无解输出"NIE"
1  < =  k, N ,M , < =1000000。


输入格式


输出格式


样例输入

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

样例输出

TAK

提示

没有写明提示


题目来源

没有写明来源