#P3475. 除草

    ID: 2687 传统题 1000ms 512MiB 尝试: 7 已通过: 5 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划树形 DP构造与建模不变量分析枚举与搜索深度优先搜索CF2200

除草

除草

题目描述

Logic_IU 和 Lao5 是 T 国的花匠。一次,两人给皇宫新建的花园除草时手艺不佳,被前来采花的 Freda 公主训斥。Logic_IU 听说 Hengzo 星的人擅长园艺,便踏上前往 Hengzo 星的旅程。

她来到 HE 星系。这里有 NN 颗星球和 MM 条双向飞行路线。管理局只会在原本无法互达的两颗星球之间新建飞行路线,并保证所有星球最终互相可达。

管理局还开设了 KK 条单向传送通道。经过一条通道就会得到该通道专属的限定人偶。即使几条通道的起点和终点相同,它们赠送的人偶也各不相同。

当地人不允许旅客回到已经离开的星球。Logic_IU 现在位于编号为 ss 的星球,Hengzo 星的编号为 tt。她想知道,能否从 ss 出发,使用每一条单向传送通道,最终到达 tt,并且每颗星球最多经过一次。

输入格式

第一行包含一个正整数 TT,表示测试组数。

每组的第一行包含三个整数 N,M,KN,M,K,分别表示星球数、双向飞行路线数和单向传送通道数。第二行包含 s,ts,t。

接下来 MM 行,每行两个整数 a,ba,b,表示 a,ba,b 之间有一条双向飞行路线;这些路线互不重复。

再接下来 KK 行,每行两个整数 a,ba,b,表示有一条从 aa 到 bb 的单向传送通道。

星球从 00 到 N−1N-1 编号。

输出格式

每组数据输出一行。存在符合要求的方案时输出 TAK,否则输出 NIE。

样例 #1

3
3 2 1
1 0
0 1
0 2
1 2
3 2 1
1 0
0 1
0 2
2 1
3 2 2
0 1
0 2
2 1
0 1
1 0
TAK
NIE
NIE

第一组可以先用从 11 到 22 的传送通道,再沿飞行路线到达终点 00。第二组要使用从 22 回到起点 11 的通道,违反了不能重复经过星球的规则。第三组的两条通道构成往返,使用两条通道会重复经过星球,起点和终点也适用这条规则。

数据范围

1≤N,M≤1051\le N,M\le 10^5,0≤K≤1050\le K\le 10^5。所有飞行路线和传送通道的两个端点互不相同。测试组数 TT 可能很大。