Charlie 的运输网

题目信息

时间限制: 1s

空间限制: 256M

输入文件: charlie.in

输出文件: charlie.out

题目描述

Charlie 是 P 国的交通大臣，P 国有 $n$ 座城市和 $m$ 条连接城市的双向道路。P 国在 Charlie 的带领下掌握了先进的交通技术，也就是说任何时候途径 P 国的任意道路能在单位时间从道路一端的城市抵达道路另一端的城市。不过这样的交通运输不具有传递性，即假设 P 国仅有三座城市 $a, b, c$ 和两条道路 $(a, b), (b, c)$，那么从 $a$ 到 $c$ 的最短时间是 $2$，而不是 $1$。

P 国的女王 Candy 对国家的交通运输网情有独钟，她要求对于 P 国交通网络的任意一棵生成树，都要保证任意连通（也就是说不连通的点对不作要求）的两座城市在原图上的最短路（耗时最短，下同）和生成树上的最短路在模 $2$ 意义下相等。

因为 Charlie 的交通技术才问世不久，所以 P 国还会再增添一些新的道路，但是 Candy 女王十分担心在新修道路的过程中自己的审美需求是否会被破坏，因此 Charlie 将要按顺序处理 $q$ 个修改或查询，形式如下：

• $1\ u\ v$，代表 P 国新修了一条道路 $(u, v)$
• $2$，代表 Candy 女王发出了一次询问，P 国目前的道路是否满足她的审美需求？如果是，请大胆地输出 YES；否则，请输出 yes，毕竟新道路成本昂贵，Candy 女王也不是不讲理的人。
• $3$，代表 Charlie 需要进行一次审计，一共有多少条道路，使得仅删除该道路后 P 国的交通网络满足 Candy 女王的审美需求？

输入格式

第 $1$ 行三个整数 $n, m, q$，表示 P 国的城市数，当前的道路数和 Charlie 要处理的事件数。

第 $2$ 至 $m+1$ 行每行两个整数 $u, v$，表示一条 P 国目前拥有的道路 $(u, v)$。

第 $m+2$ 至 $m+q+1$ 行每行若干整数表示一个 Charlie 需要处理的事件，格式如题目描述所示。

保证 P 国的道路在任意时刻没有重边和自环。

输出格式

对于每一个 $2$ 或 $3$ 操作输出答案，格式如题目描述所示。

样例

样例输入1

4 4 7
1 2
2 3
3 4
4 1
3
2
1 1 3
2
3
1 2 4
3

样例输出1

4
YES
yes
1
0

样例解释1

• 对于第一个询问 $3$：所有边都满足条件。
• 对于第二个询问 $2$：当前 P 国只有唯一的一棵生成树，生成树上任意两点的最短路就是原图的最短路，因此耗时在模 $2$ 意义下相等，应当输出 YES。
• 对于第三个询问 $2$：当选取的树边是 $(1, 2), (1, 3), (3, 4)$ 时，$(1, 4)$ 在原图上的最短路耗时为 $1$，在树上的最短路耗时为 $2$，模 $2$ 意义下不相同，因此应当输出 yes。
• 对于第四个询问 $3$：仅有道路 $(1, 3)$ 满足条件。
• 对于第五个询问 $3$：所有道路都不满足条件，例如对于删除 $(1, 3)$ 之后的图，当选取的树边是 $(1, 2), (2, 4), (3, 4)$ 时，$(2, 3)$ 在原图上的最短路耗时为 $1$，在树上的最短路耗时为 $2$，模 $2$ 意义下不相同。

数据范围与提示

• 对于测试点 1~2，保证 $n, m, q\leq 5$
• 对于测试点 3~5，保证 $n, m, q\leq 300$
• 对于测试点 6~8，保证没有操作 $3$
• 对于测试点 9~12，保证没有操作 $1$
• 对于测试点 13~16，保证 $q\leq 10^5$
• 对于测试点 17~20，没有特殊的限制。
• 对于所有数据，$1\leq n, m\leq 10^5, 1\leq q\leq 10^6, 1\leq u, v\leq n$，且任意时刻 P 国无重边和自环。