题目描述

有N个岔路口、M条单向街道。无自环，每一有序点对最多一条街道。邮递员需要从1出发，每条街道恰好经过一次，最后回到1。

此外给定t个路口序列片段，每个片段都必须在完整路线的路口序列中连续出现。本地规范采用线性片段语义：完整路线写成v_0,v_1,...,v_M，其中v_0=v_M=1；片段必须等于其中某个连续区间，不能越过v_M再连接v_1。片段允许相互重叠、重复给出；同一街道仍只能经过一次。片段若含不存在的街道也视为不可能。

只需判断是否存在满足全部要求的路线。

输入

第一行N,M。接下来M行a,b表示a→b。随后一行t，接下来t行先输入k，再输入k个路口编号。

输出

存在输出TAK，否则输出NIE。

数据范围

2≤N≤50000，1≤M≤200000，1≤a,b≤N且a≠b，无重边；0≤t≤10000，2≤k≤200000，所有片段长度之和≤1000000。允许不连通和非平衡图，由程序判断是否有解。

输入样例

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