#P3443. [POI2006] LIS-The Postman

[POI2006] LIS-The Postman

题目描述

每天早上,忙碌的邮递员需要经过城市的所有街道,完成投递邮件的任务。城市内的所有道路都是单向的,并通过一些路口连接起来。两个路口 u,vu,v 最多只有两条道路直接相连:一条 uvu \to v,一条 vuv \to u(也即不存在两条 uvu \to v 的街道)。所有路口从 11nn 编号。

在路口 11,邮递员可以开始他的行程,或是结束他的行程。很长的一段时间里,邮递员可以随意选择他的路线,但最近新出的一条规定打乱了他的计划:每个邮递员得到了若干组路口序列,现在邮递员的路线必须满足如下要求:

  • 路线必须从路口 11 开始,在路口 11 结束。
  • 路线必须经过每条街道恰好一次。
  • 规定的每个路口序列都必须在路线中连续出现。例如:1 2 1 这个序列在 1 2 1 3 中出现了,而在 1 2 3 1 中没有出现(不是连续的)。

现在邮递员找到了你,希望你能告诉他是否存在满足上述条件的路线,如果有的话,也请告诉他一条满足要求的路线。

输入格式

输入第一行两个整数 n,mn,m,分别为路口数和街道数。

接下来 mm 行,每行两个整数 a,ba,b,表示存在一条 aba \to b 的街道。保证相同的街道不会重复给出,也不会有自环。

下一行一个整数 tt,代表规定的路口序列数。

接下来 tt 行,每行第一个整数 kk,接下来 kk 个数,代表一个规定的路口序列。

输出格式

如果存在一个满足条件的路线,输出 TAK,否则输出 NIE

如果答案是 TAK 的话,请在接下来每行输出一个整数,代表一个满足条件的路线。

设你输出了 m+1m+1 个数,输出的第 ii 个数为 viv_i,你的输出需要满足如下条件:

  • v1=vm+1=1v_1=v_{m+1}=1
  • 1im\forall 1 \leq i \leq m,都存在 viv_ivi+1v_{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

提示

所有数据均满足:2n5×1042 \leq n \leq 5 \times 10^41m2×1051 \leq m \leq 2 \times 10^51a,bn1 \leq a,b \leq naba \neq b0t1040 \leq t \leq 10^42k1052 \leq k \leq 10^5k105\sum k \leq 10^5