1515 - [POI2006]Lis-The Postman

每天早上邮递员都要走过每条街道来递送邮件. 所有的道路都是单向的. 两个岔路口间最多有两条边并且方向不同. 岔路口从1 到 编号. 邮递员从Byteotian邮政总部出发并且最终回到总部, 他可以自由选择自己喜欢的线路.最近他的上司给了他新的任务. 他被分派了一些路径的片段- 即一些需要依次经过的岔路口序列. 邮递员要选择一条路径使得: · 经过每条街道一次, · 包含所有给定的路径片段, · 从第一个路口出发并回到第一个路口. 很不幸,很可能这样的路径不一定存在. 请你帮邮递员找出一条可行的路径.

输入

第一行两个整数N和M,2<=N<=50000,1<=M<=200000 表示岔路口数目以及街道的数目. 接下来M行每行两个数字a, b, 1<=a,b<=N,a<>b,, 表示一条单向道路. 每一队 a,b在数据中最多出现一次. 接下来一行一个整数t,0<=t<=10000 表示给定的路径片段数目. 接下来t行用来描述这些路径片段. 每行开始一个整数 k,2<=K<=200000, 并且一个序列 v1,v2…vk表示需要经过的路口总数以及这些路口的编号. 所有路径片段的总长不超过1000000.

输出

第一行输出: · TAK - 如果存在一条满足条件的路径, · NIE – 如果路径不存在.

样例

输入

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

输出

TAK
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题