P12741 [POI 2016 R3] 等价程序 Equivalent programs

翻译来自于 [LibreOJ](https://loj.ac/p/5037)。

**题目译自 [XXIII Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi23-3/dashboard/) [Równoważne programy](https://szkopul.edu.pl/problemset/problem/SlqBmJqSmy7cVbTMEIVt3kyp/statement/)** 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`。

**样例 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$。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 5$ | $5$ | | $2$ | $k \leq 2$ | $5$ | | $3$ | $n \leq 1000$ | $25$ | | $4$ | 无附加限制 | $65$ |