[POI2006]Lis-The Postman

内存限制：259 MiB 时间限制：10 Sec

每天早上邮递员都要走过每条街道来递送邮件. 所有的道路都是单向的. 两个岔路口间最多有两条边并且方向不同. 岔路口从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 – 如果路径不存在.

样例输入

样例输出

TAK

#1515. [POI2006]Lis-The Postman

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示