어려운 선택

바이트아사르는 결정을 잘 내리지 못한다. 바이트타운을 지날 때 출발지와 목적지 사이에 완전히 다른 경로가 두 개 이상 있으면, 그중 하나를 고르는 데 한참이 걸린다. 그는 바이트타운에 도로 공사가 예정되어 있다는 소식을 들었는데, 아마 이 소식을 반기는 유일한 주민일 것이다. 일부 거리가 폐쇄되면 이런 괴로운 선택을 하지 않아도 될지 모르기 때문이다.

바이트타운에는 $n$개의 교차로가 $m$개의 양방향 거리로 연결되어 있다. 같은 두 교차로를 잇는 두 경로가 공유하는 거리가 하나도 없을 때, 두 경로를 서로 완전히 다른 경로라고 부른다. 단, 두 경로가 같은 교차로를 지나는 것은 허용된다.

거리가 하나씩 폐쇄되는 동안, 바이트아사르는 특정 교차로 쌍에 대해 (아직 열려 있는 거리만 사용해서) 완전히 다른 경로가 여전히 두 개 이상 존재하는지 알고 싶어 한다. 그의 질문에 답하는 프로그램을 작성하여라.

첫째 줄에 세 정수 $n$, $m$, $z$가 주어진다 ($2 \le n \le 100\,000$, $1 \le m, z \le 100\,000$). 각각 교차로의 수, 거리의 수, 사건의 수이다. 교차로는 $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 \{Z, P\}$, $1 \le c_i, d_i \le n$, $c_i \ne d_i$). 사건은 시간 순서대로 주어진다.

• $t_i = Z$: 교차로 $c_i$와 $d_i$를 잇는 거리가 폐쇄된다. 이 거리는 반드시 존재하며 이전에 폐쇄된 적이 없음이 보장된다. 폐쇄는 임의의 순서로 일어날 수 있으며, 어느 순간에는 바이트타운의 모든 거리가 폐쇄될 수도 있다.
• $t_i = P$: 바이트아사르가 교차로 $c_i$에서 $d_i$로 이동하려 하며, 아직 열려 있는 거리만 사용해서 완전히 다른 두 경로로 이동할 수 있는지 묻는다.

$P$ 유형의 사건마다 한 줄씩, 입력에 나타난 순서대로 출력한다. 주어진 두 교차로 사이에 서로 겹치는 거리가 없는 두 경로가 존재하면 TAK(폴란드어로 "예")를, 그렇지 않으면 NIE(폴란드어로 "아니오")를 출력한다. $P$ 유형의 사건은 적어도 하나 존재함이 보장된다.