[AdditionalFile5502.zip](file://AdditionalFile5502.zip?type=additional_file)

#5502. 「POI2006 R2」邮递员 The Postman

标签: 传统 | 时间限制: 1500 ms | 内存限制: 64 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – II etap Listonosz

邮递员 Bajtazar 每天都必须走遍他负责区域内的所有街道以派送邮件。所有的街道都是单行道，连接着（成对不同的）十字路口。一对十字路口之间最多可以有两条街道相连：一条为一个方向，另一条为相反方向。十字路口的编号从 $1$ 到 $n$。

Bajtazar 在位于 $1$ 号十字路口的字节邮政总局开始并结束他的路线。长久以来，Bajtazar 都是自己选择路线来巡视他的区域，但最近邮局管理层发布了一项新规定，限制了路线选择的自由。每位邮递员都被分配了一套特定的路线片段——即一组十字路口的序列。Bajtazar 必须选择一条满足以下条件的路线：

• 每条街道都必须且仅经过一次，
• 路线中必须包含所有给定的序列（作为连续的子序列），
• 路线必须在 $1$ 号十字路口开始和结束。

不幸的是，管理层发布的规定可能导致不存在满足要求的 Bajtazar 路线，例如，某个序列可能要求他走一条根本不存在的道路。请帮助 Bajtazar，编写一个程序来检查是否存在符合要求的路线，如果存在，则找出这条路线。

请编写一个程序，实现以下功能：

• 从标准输入读取街道描述和分配的序列，
• 检查 Bajtazar 是否能够巡视他的区域，使得每条街道都恰好经过一次，并且满足管理层的所有规定，
• 将找到的路线输出到标准输出，或指出这样的路线不存在。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(2 \le n \le 50000, 1 \le m \le 200000)$，由单个空格隔开，分别表示十字路口和街道的数量。 接下来的 $m$ 行是街道的描述：每行包含两个整数 $a, b$ $(1 \le a, b \le n, a \neq b)$，由单个空格隔开，表示有一条从十字路口 $a$ 到 $b$ 的（单向）街道。每个（有序的）数对 $a,b$ 在数据中最多出现一次。

再下一行包含一个整数 $t$ $(0 \le t \le 10000)$，表示规定的序列数量。

接下来的 $t$ 行是序列的描述。每个序列的描述由一个数字 $k$ $(2 \le k \le 200000)$ 和 $k$ 个十字路口编号的序列 $v_1, \ldots, v_k$ 组成。行内的数字由单个空格隔开。所有序列的总长度不超过 $1000000$。

输出格式

你的程序应在输出的第一行输出：

• TAK - 如果存在满足条件的路线，
• NIE - 如果这样的路线不存在。

如果答案是 TAK，则在接下来的行中应输出出找到的路线描述。如果存在多条这样的路线，可以输出其中任意一条。路线描述应由邮递员路线上依次访问的 $m+1$ 个十字路口编号序列 $v_1, \ldots, v_{m+1}$ 组成，每个编号占一行，且满足：

• $v_1 = v_{m+1} = 1$，
• 对于 $1 \le i \le m$，存在一条从 $v_i$ 到 $v_{i+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

输出

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