题目描述

有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

本地修订说明

本题依据一本通公开条目整理，并按用户授权补全或修正题面约定，不冒称原站/官方原版完整题面。原页未区分片段跨回路首尾是否可视为出现；本地明确线性M+1路口序列、片段不跨首尾，重复可重叠，无路边片段NIE。该语义可能较环形片段解释严格，显式披露不冒称官方。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：原页未区分片段跨回路首尾是否可视为出现；本地明确线性M+1路口序列、片段不跨首尾，重复可重叠，无路边片段NIE。该语义可能较环形片段解释严格，显式披露不冒称官方。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1737。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。