P6351 [PA 2011] Hard Choice

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.

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.

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.

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