忙碌的邮递员 ### 题目描述 每天早上，忙碌的邮递员需要经过城市的所有街道，完成投递邮件的任务。城市内的所有道路都是单向的，并通过一些路口连接起来。两个路口 $u,v$ 最多只有两条道路直接相连：一条 $u \to v$，一条 $v \to u$（也即不存在两条 $u \to v$ 的街道）。所有路口从 $1$ 到 $n$ 编号。 在路口 $1$，邮递员可以开始他的行程，或是结束他的行程。很长的一段时间里，邮递员可以随意选择他的路线，但最近新出的一条规定打乱了他的计划：每个邮递员得到了若干组路口序列，现在邮递员的路线必须满足如下要求： - 路线必须从路口 $1$ 开始，在路口 $1$ 结束。 - 路线必须经过每条街道**恰好**一次。 - 规定的每个路口序列都必须在路线中**连续**出现。例如：`1 2 1` 这个序列在 `1 2 1 3` 中出现了，而在 `1 2 3 1` 中没有出现（不是连续的）。 现在邮递员找到了你，希望你能告诉他是否存在满足上述条件的路线，如果有的话，也请告诉他一条满足要求的路线。 ### 输入描述 输入第一行两个整数 $n,m$，分别为路口数和街道数。 接下来 $m$ 行，每行两个整数 $a,b$，表示存在一条 $a \to b$ 的街道。保证相同的街道不会重复给出，也不会有自环。 下一行一个整数 $t$，代表规定的路口序列数。 接下来 $t$ 行，每行第一个整数 $k$，接下来 $k$ 个数，代表一个规定的路口序列。 其中，$2 \leq n \leq 5 \times 10^4$，$1 \leq m \leq 2 \times 10^5$，$1 \leq a,b \leq n$，$a \neq b$，$0 \leq t \leq 10^4$，$2 \leq k \leq 10^5$，$\sum k \leq 10^5$。 ### 输出描述 如果存在一个满足条件的路线，输出 `TAK`，否则输出 `NIE`。 ### 输入输出样例 #### 示例 >输入 ```txt 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 ``` >输出 ```txt TAK ```