#P1515. [POI2006]Lis-The Postman

    ID: 527 传统题 1000ms 512MiB 尝试: 256 已通过: 56 难度: 7 上传者: 标签>CF2200提高+/省选-强制相邻链压缩欧拉回路Hierholzer 算法二分查找

[POI2006]Lis-The Postman

[POI2006] LIS-The Postman

题目描述

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

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

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

现在邮递员找到了你,希望你能告诉他是否存在满足上述条件的路线,只需判断是否存在。

输入格式

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

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

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

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

输出格式

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

本地评测采用判定版本:只输出这一行,不输出具体路线。

样例 #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

提示

所有数据均满足:2≤n≤5×1042 \leq n \leq 5 \times 10^4,1≤m≤2×1051 \leq m \leq 2 \times 10^5,1≤a,b≤n1 \leq a,b \leq n,a≠ba \neq b,0≤t≤1040 \leq t \leq 10^4,2≤k≤1052 \leq k \leq 10^5,∑k≤105\sum k \leq 10^5。