题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIII Olimpiada Informatyczna — III etap Równoważne programy

Byteasar 最近入手了一台新电脑，正热衷于学习编程。程序是由一系列指令组成的序列，指令共有 $k$ 种，为方便起见，编号为 $1$ 至 $k$。某些指令对具有交换性，即如果它们在程序中相邻（无论顺序），交换它们的位置会得到一个行为相同的等价程序。其余不具备此性质的指令对则称为互斥指令对。Byteasar 已经编写了两个包含 $n$ 个指令的程序，他很好奇这两个程序是否等价。请帮助他解答！

输入格式

第一行包含三个整数 $n, k, m$，分别表示两个程序的指令数量、指令种类数和互斥指令对的数量。

接下来的 $m$ 行描述互斥指令对，每行包含两个整数 $a_i, b_i$ $(1 \leq a_i < b_i \leq k)$，表示指令 $a_i$ 和 $b_i$ 构成互斥对。保证每对指令至多出现一次。

最后两行描述两个程序，每行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$ $(1 \leq c_i \leq k)$，表示程序中指令的编号序列指令的编号。

输出格式

输出一行，包含一个单词：若输入的两个程序等价，输出 TAK；否则输出 NIE。

5 3 1
2 3
1 1 2 1 3
1 2 3 1 1

TAK

3 3 1
2 3
1 2 3
3 2 1

NIE

提示

样例 1 解释

通过以下交换序列将第一个程序转换为第二个程序：$(2,3), (4,5), (3,4)$，其中 $(i, i+1)$ 表示交换当前序列中第 $i$ 和第 $i+1)$ 条指令。

附加样例

1. $n=50, k=50, m=1$，程序为 $(1,2, \ldots, 49,50)$ 和 $(50,49, \ldots, 2,1)$，答案为 NIE。
2. $n=99999, k=3, m=1$，互斥指令为 $1$ 和 $2$，程序为 $(1,2,3,1,2,3, \ldots)$ 和 $(3,1,2,3,1,2, \ldots)$，答案为 TAK。
3. $n=100000, k=1000, m=50000$，程序为 $(13,13, \ldots,13)$ 和 $(37,37, \ldots,37)$，答案为 NIE。

所有测试数据满足 $1 \leq n \leq 100000, 1 \leq k \leq 1000, 0 \leq m \leq 50000$。

详细子任务附加限制及分值如下表所示。