UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3069. [Pa2011]Hard Choice 艰难的选择

Statistics 下载数据

Description

Byteasar是一个很纠结的人。每次他经过Bytetown的时候都知道有至少2条不同的路径可以选择,这导致他必须花很长时间来决定走哪条路。Byteasar最近听说了Bytetown的修路计划,他可能是唯一一个为此感到高兴的人——他有机会消除他的烦恼。

在Byteasar一共有n个岔口,连接着m条双向道路。两条路径完全不同当且仅当他们没有公共的道路(但是允许经过相同的岔口)。

Byteasar想知道:对于两个岔口x y,是否存在一对完全不同的路径。

Input

第一行3个整数:n, m, z (2<=n<=100000, 1<=m,z<=100000),分别代表:n个岔口,m条边,事件数z。岔口编号为1~n。

下面m行:ai, bi (1<=ai,bi<= n, ai!=bi),描述一条边

然后下面z行描述事件:ti, ci, di (t='Z' or 'P', 1<=ci,di<=n, ci!=di)。事件按照时间排序。

  • t='Z',表示删除一条边(ci, di),保证这条边之前没有被删除。注意,边可以被全部删除!
  • t='P',询问是否存在从ci到di的一对完全不同的路径。

Output

对于每组询问,如果存在,输出TAK,否则输出NIE

Sample Input

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

Sample Output

TAK
TAK
NIE
NIE

Hint

Source