Description

There is an undirected graph with $n$ vertices and $m$ edges.

There are $q$ queries. Each query contains a character $opt$ and two integers $x, y$.

If $opt$ is $Z$, it means a deletion operation: delete the edge $(x, y)$. It is guaranteed that the edge $(x, y)$ has not been deleted before, but it is not guaranteed that the edge exists in the current graph (that is, it is possible to delete all edges).

If $opt$ is $P$, it means a query: ask whether there are two completely different paths between $x$ and $y$. “Completely different” means the two paths do not share any edge, but they may share vertices.

Input Format

The first line contains three integers $n, m, q$, with the same meaning as in the statement.

The next $m$ lines each contain two integers $x, y$, indicating that there is an undirected edge between $x$ and $y$.

The next $q$ lines each contain a character $opt$ and two integers $x, y$, with the same meaning as in the statement.

Output Format

For each query with $opt$ equal to $P$, if there exist two completely different paths, output one line with the string TAK. Otherwise, output one line with the string 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

Hint

Constraints: $2\leq n\leq 10^5$, $1\leq m,q\leq 10^5$. It is guaranteed that the input is valid and there are no multiple edges or self-loops.

Translated by ChatGPT 5