[Pa2011]Hard Choice 艰难的选择
时间限制：10s 空间限制：128MB
题目描述
Byteasar是一个很纠结的人。每次他经过Bytetown的时候都知道有至少2条不同的路径可以选择，这导致他必须花很长时间来决定走哪条路。Byteasar最近听说了Bytetown的修路计划，他可能是唯一一个为此感到高兴的人——他有机会消除他的烦恼。
在Byteasar一共有n个岔口，连接着m条双向道路。两条路径完全不同当且仅当他们没有公共的道路（但是允许经过相同的岔口）。
Byteasar想知道：对于两个岔口x y，是否存在一对完全不同的路径。
输入格式
第一行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的一对完全不同的路径。
输出格式
对于每组询问，如果存在，输出TAK，否则输出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
提示
没有写明提示
题目来源
没有写明来源