#P3475. 除草
除草
除草
题目描述
Logic_IU 和 Lao5 是 T 国的花匠。一次,两人给皇宫新建的花园除草时手艺不佳,被前来采花的 Freda 公主训斥。Logic_IU 听说 Hengzo 星的人擅长园艺,便踏上前往 Hengzo 星的旅程。
她来到 HE 星系。这里有 颗星球和 条双向飞行路线。管理局只会在原本无法互达的两颗星球之间新建飞行路线,并保证所有星球最终互相可达。
管理局还开设了 条单向传送通道。经过一条通道就会得到该通道专属的限定人偶。即使几条通道的起点和终点相同,它们赠送的人偶也各不相同。
当地人不允许旅客回到已经离开的星球。Logic_IU 现在位于编号为 的星球,Hengzo 星的编号为 。她想知道,能否从 出发,使用每一条单向传送通道,最终到达 ,并且每颗星球最多经过一次。
输入格式
第一行包含一个正整数 ,表示测试组数。
每组的第一行包含三个整数 ,分别表示星球数、双向飞行路线数和单向传送通道数。第二行包含 。
接下来 行,每行两个整数 ,表示 之间有一条双向飞行路线;这些路线互不重复。
再接下来 行,每行两个整数 ,表示有一条从 到 的单向传送通道。
星球从 到 编号。
输出格式
每组数据输出一行。存在符合要求的方案时输出 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
第一组可以先用从 到 的传送通道,再沿飞行路线到达终点 。第二组要使用从 回到起点 的通道,违反了不能重复经过星球的规则。第三组的两条通道构成往返,使用两条通道会重复经过星球,起点和终点也适用这条规则。
数据范围
,。所有飞行路线和传送通道的两个端点互不相同。测试组数 可能很大。