题目描述

在国家 X 中，有 $n$ 座城市和 $m$ 条道路。道路集合有两个有趣的性质：

1. 所有道路都是单向道路；
2. 如果忽略道路方向，把所有道路看成无向边，那么任意两座城市之间最多只有一条简单路径。

因此，忽略方向后，这张图是一片森林：在每个连通分量中，边数比点数少 $1$。

定义函数 $cost(u,v)$ 如下：

• 如果存在从 $u$ 到 $v$ 的有向路径，那么 $cost(u,v)$ 等于这条路径上的道路数量；
• 如果不存在从 $u$ 到 $v$ 的有向路径，那么 $cost(u,v)=0$。

国家地图的美观度定义为：

政府希望计算当前地图的美观度，并处理 $q$ 次修改。每次修改后，都需要重新输出地图美观度。

修改有四种类型：

1. 添加一条从城市 $u$ 到城市 $v$ 的道路。
2. 删除城市 $u$ 和城市 $v$ 之间的道路。
3. 反转城市 $u$ 和城市 $v$ 之间道路的方向。
4. 将从城市 $u$ 到城市 $v$ 的路径上的所有道路都定向为从 $u$ 指向 $v$。保证忽略方向后，$u$ 到 $v$ 之间存在路径，所以这个操作可行。

保证每次修改后，城市和道路组成的无向图仍然是一片森林。

注意，本题中的询问会真正修改地图，后续询问基于前面修改后的结果。

输入格式

第一行包含一个整数 $g$（$0 \le g \le 10$），表示测试组编号。

第二行包含三个整数 $n,m,q$（$2 \le n \le 400000$，$0 \le m < n$，$1 \le q \le 400000$），分别表示城市数、初始道路数和修改次数。

接下来 $m$ 行，每行包含两个整数 $u,v$（$1 \le u,v \le n$），表示初始地图中有一条从 $u$ 到 $v$ 的有向道路。

接下来 $q$ 行，每行包含三个整数 $t,u,v$（$1 \le t \le 4$，$1 \le u,v \le n$），表示一次修改的类型和相关顶点。

输出格式

第一行输出初始地图的美观度。

接下来 $q$ 行，每行输出一次修改后的地图美观度。

样例 #1

样例输入 #1

0
5 4 4
1 2
2 3
3 4
4 5
3 4 3
2 3 2
1 4 2
4 1 4

样例输出 #1

20
6
3
4
16

样例解释

初始图，城市 $1,2,3,4,5$ 形成一条路径，边方向依次为 $1\to2\to3\to4\to5$。

例如，$cost(1,2)=cost(2,3)=cost(3,4)=cost(4,5)=1$，因为这些点对之间有直接道路。类似地，$cost(1,3)=cost(2,4)=cost(3,5)=2$，因为需要经过两条道路才能到达。另一方面，例如 $cost(2,1)=cost(4,1)=cost(5,3)=0$，因为后者不能从前者到达。对所有有序点对求和，得到 $20$。

第一次修改需要反转城市 $3$ 和城市 $4$ 之间道路的方向。原来方向是 $3\to4$，修改后变为 $4\to3$。此时答案为 $6$。

此处应插入原题图：第一次修改后的图。

接着删除城市 $2$ 与城市 $3$ 之间的道路。此时答案为 $3$。

之后添加一条从城市 $4$ 到城市 $2$ 的道路。此时答案为 $4$。

第三次修改后的图。

最后，将城市 $1$ 到城市 $4$ 路径上的所有道路都定向为从 $1$ 指向 $4$。此时答案为 $16$。

此处应插入原题图：第四次修改后的图。

评分方式

测试数据包含 10 个测试组。只有通过该组以及若干指定的前置测试组，才能获得该组分数。Offline-testing 表示该组结果只会在比赛结束后公布。