邮递员

【题目描述】

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

【输入】

第一行两个整数$N$和$M$，表示岔路口数目以及街道的数目。 接下来$M$行每行两个数字$a, b$，表示一条单向道路。每一对 $a,b$在数据中最多出现一次。 接下来一行一个整数$t$, 表示给定的路径片段数目。 接下来$t$行用来描述这些路径片段。 每行开始一个整数 $k$, 并且一个序列$v_1,v_2,…,v_k$表示需要经过的路口总数以及这些路口的编号。

【输出】

第一行输出: $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

【提示】

【数据规模】 对于100%的数据，$2≤N≤50000，1≤M≤200000，1≤a,b≤N（a≠b），0≤t≤10000，2≤K≤200000$，所有路径片段的总长不超过$1000000$。