Byteasar 一直在为做决定而苦恼。每当他在 Bytetown 旅行时，如果发现至少有两条完全不同的路线可供选择，他总是要花很长时间才能决定走哪一条。最近，Byteasar 听说 Bytetown 计划进行道路施工。他可能是城里唯一一个为此感到高兴的人：道路封闭或许能减轻他做决定的痛苦。

在 Bytetown 有 $n$ 个路口，由 $m$ 条双向街道连接。如果两条连接给定路口对的路线不共享任何街道，则称它们是完全不同的。然而，这些路线可以经过相同的路口。

Byteasar 正在密切关注道路封闭的情况。起初，他还能检查给定路口对之间是否存在至少两条完全不同的路线，但随着时间的推移，更新这些数据对他来说变得困难了。你能写一个程序来帮助他解决这个问题吗？

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $z$ ($2 \le n \le 100\,000$，$1 \le m, z \le 100\,000$)，分别表示 Bytetown 的路口数量、街道数量和事件数量。路口编号为 $1$ 到 $n$。

接下来的 $m$ 行包含街道的描述，每行包含两个整数 $a_{i}$、$b_{i}$ ($1 \le a_{i}, b_{i} \le n$，$a_{i} \ne b_{i}$)。每一对整数表示连接路口 $a_{i}$ 和 $b_{i}$ 的一条双向街道。每对路口之间最多只有一条街道。

接下来的 $z$ 行包含事件的描述，每行包含一个字符 $t_{i}$ 和两个整数 $c_{i}$、$d_{i}$ ($t_{i} \in \{\texttt{Z}, \texttt{P}\}$，$1 \le c_{i}, d_{i} \le n$，$c_{i} \ne d_{i}$)。事件按时间顺序排列。当 $t_{i} = \texttt{Z}$ 时，表示连接路口 $c_{i}$ 和 $d_{i}$ 的街道被封闭。你可以假设该街道确实存在，且此前从未被封闭过。注意，道路施工可能以混乱的方式进行——特别是在某些时刻，Bytetown 的所有街道都可能被封闭！另一方面，当 $t_{i} = \texttt{P}$ 时，表示 Byteasar 想要在路口 $c_{i}$ 和 $d_{i}$ 之间旅行，因此他想知道是否至少有两条完全不同的路线（他只能使用尚未封闭的街道）。

输出格式

对于每个类型为 $\texttt{P}$ 的事件，按输入顺序输出一行。如果连接给定路口对的两条路线所经过的街道集合不相交，则输出 TAK（波兰语中的“是”）。否则，输出 NIE（波兰语中的“否”）。你可以假设输出不会为空。

样例

样例输入 1

7 8 7
1 2
1 3
1 4
2 3
3 4
3 7
7 4
5 6
Z 1 4
P 1 3
P 2 4
Z 1 3
P 1 3
Z 6 5
P 5 6

样例输出 1

TAK
TAK
NIE
NIE