#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  

数据范围与提示