[POI2006] LIS-The Postman
题目描述
每天早上,忙碌的邮递员需要经过城市的所有街道,完成投递邮件的任务。城市内的所有道路都是单向的,并通过一些路口连接起来。两个路口 $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$ 个数,代表一个规定的路口序列。
输出格式
如果存在一个满足条件的路线,输出 `TAK`,否则输出 `NIE`。
如果答案是 `TAK` 的话,请在接下来每行输出一个整数,代表一个满足条件的路线。
设你输出了 $m+1$ 个数,输出的第 $i$ 个数为 $v_i$,你的输出需要满足如下条件:
- $v_1=v_{m+1}=1$。
- $\forall 1 \leq i \leq m$,都存在 $v_i$ 到 $v_{i+1}$ 的街道。
- 城市中的每条街道**恰好**出现一次。
- 规定的每个路口序列都必须在路线中**连续**出现。
输入输出样例
输入样例 #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
说明
所有数据均满足:$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$。