每天早晨，邮递员 Byteasar 都必须走遍他所在区域的每一条街道去投递邮件。所有的道路都是单向的，并通过（两两不同的）十字路口连接。一对十字路口之间最多有两条道路：每个方向各一条。十字路口编号从 $1$ 到 $n$。

Byteasar 的每条路线都从位于第一个十字路口的 Byteotian 邮政总部出发，并回到这里。在 Byteasar 的记忆中，他一直都是自己选择路线，但最近董事会发布了一项新规定，限制了路线选择的自由。每位邮递员都被分配了一组路线片段——即一系列十字路口的序列。Byteasar 必须选择一条满足以下条件的路线：

• 每条街道恰好经过一次，
• 包含所有分配的序列（作为连续子序列），
• 从第一个十字路口出发并回到第一个十字路口。

遗憾的是，董事会发布的规定可能导致不存在满足要求的路线（例如，序列中要求经过一条不存在的道路）。请帮助 Byteasar 编写一个程序，验证是否存在合法的路线，如果存在，则将其找出来。

编写一个程序，完成以下任务：

• 从输入文件中读取街道和分配序列的描述，
• 验证 Byteasar 是否能够以一种既能恰好经过每条街道一次，又能满足董事会分配要求的方式走遍他的区域，
• 将找到的路线写入输出文件，或者得出不存在此类路线的结论。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$，中间用空格隔开，$2 \le n \le 50\,000$，$1 \le m \le 200\,000$，分别表示十字路口和道路的数量。接下来的 $m$ 行包含道路的描述：两个整数 $a$ 和 $b$，中间用空格隔开，$1 \le a, b \le n$，$a \ne b$，表示一条从十字路口 $a$ 到 $b$ 的单向道路。每对（有序）$a, b$ 在数据中最多出现一次。接下来的行中有一个整数 $t$，$0 \le t \le 10\,000$，表示分配的序列数量。随后的 $t$ 行包含这些序列的描述。描述由一个整数 $k$（$2 \le k \le 200\,000$）和 $k$ 个十字路口编号组成的序列构成。行内的数字由空格隔开。所有序列的总长度不超过 $1\,000\,000$。

输出格式

你的程序应在输出文件的第一行写入：

• TAK（波兰语中的“是”）——如果存在满足任务要求的路线，
• NIE（波兰语中的“否”）——如果不存在此类路线。

如果答案为 TAK，接下来的行应包含所找到路线的描述。如果存在多条此类路线，输出其中任意一条即可。描述由邮递员在路线上访问的十字路口序列组成——共 $m+1$ 个数字：$v_1, \dots, v_{m+1}$，每个数字占一行，满足：

• $v_1 = v_{m+1} = 1$，
• $v_i$ 和 $v_{i+1}$（对于 $1 \le i \le m$）之间由一条街道连接，
• 每条街道在列表中恰好出现一次，
• 该路线包含董事会规定的所有序列作为连续子序列。

样例

输入 1

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

输出 1

TAK
1
3
4
3
6
4
1
5
6
2
1