Hard Choice

Byteasar has always had trouble making decisions. Whenever he travels through Bytetown and there are at least two totally different possible routes between his origin and destination, it takes him ages to settle on one. He recently heard that roadworks are planned in Bytetown, and he is perhaps the only resident glad about it: closing some streets might spare him these agonizing choices.

Bytetown has $n$ junctions connected by $m$ bidirectional streets. Two routes between the same pair of junctions are called totally different if they share no street. Such routes may still pass through common junctions.

As the streets are closed one by one, Byteasar wants to know, for selected pairs of junctions, whether there still exist at least two totally different routes between them (using only the streets that are still open). Write a program that answers his questions.

The first line contains three integers $n$, $m$, and $z$ ($2 \le n \le 100\,000$, $1 \le m, z \le 100\,000$): the number of junctions, the number of streets, and the number of events. The junctions are numbered from $1$ to $n$.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), describing a bidirectional street between junctions $a_i$ and $b_i$. Every pair of junctions is joined by at most one street.

Each of the following $z$ lines describes one event as a letter $t_i$ and two integers $c_i$ and $d_i$ ($t_i \in \{Z, P\}$, $1 \le c_i, d_i \le n$, $c_i \ne d_i$). Events are given in chronological order.

• $t_i = Z$: the street between junctions $c_i$ and $d_i$ is closed. This street is guaranteed to exist and to have never been closed before. Closures may happen in any order, and at some moment every street in Bytetown might be closed.
• $t_i = P$: Byteasar wants to travel between junctions $c_i$ and $d_i$ and asks whether he can do so along at least two totally different routes, using only the streets that are still open.

For every event of type $P$, output one line, in the order the events appear in the input. Print TAK (Polish for "yes") if there exist two routes between the given junctions that use disjoint sets of streets, and NIE (Polish for "no") otherwise. At least one event of type $P$ is guaranteed.