题目描述

有一个 $n$ 个点，$m$ 条边的无向图。

有 $q$ 次询问，每次询问包含一个字符 $opt$ 和两个整数 $x,y$。

若 $opt$ 为 $Z$，表示一次删除操作，删去边 $x,y$，保证 $x,y$ 这条边之前没有被删除，但不保证图上存在边（也就是说，可能会删去所有的边）。

若 $opt$ 为 $P$，表示一次询问，询问 $x,y$ 之间是否有两条完全不同的路径，这里的完全不同指没有经过相同的边，但可以经过相同的点。

输入格式

第一行三个整数 $n,m,q$，意义同题面。

接下来 $m$ 行，每行两个数 $x,y$，表示 $x,y$ 之间存在一条无向边。

接下来 $q$ 行，每行包含一个字符 $opt$ 和两个整数 $x,y$，意义同题面。

输出格式

对于每一次 $opt$ 为 $P$ 的询问，如果存在两条完全不同的路径，输出一行一个字符串 TAK，否则输出一行一个字符串 NIE。

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

TAK
TAK
NIE
NIE

提示

$2\leq n\leq 10^5$，$1\leq m,q\leq 10^5$，保证输入数据合法且不存在重边和自环。