对于一棵无权树 $T$，如果不存在比简单路径 $P$ 更长的简单路径，则称 $P$ 为直径。如果两条路径包含的顶点集合不同，则称它们是不同的。

考虑路径集合 $D_T$，其中 $P \in D_T$ 当且仅当 $P$ 是一条直径。给定两条路径 $D$ 和 $E$，令 $f(D, E)$ 为同时属于 $D$ 和 $E$ 的顶点数量。

给定一个包含 $N$ 个顶点和 $M$ 条边的无向森林（无环图）。处理 $Q$ 个如下形式的查询：

• “1 $x$ $y$”：连接顶点 $x$ 和 $y$（$1 \le x, y \le N$）。保证查询时 $x$ 和 $y$ 之间没有路径。
• “2 $x$ $y$”：删除顶点 $x$ 和 $y$ 之间的边（$1 \le x, y \le N$）。保证查询时该边存在。
• “3 $x$”：令 $F$ 为包含顶点 $x$ 的连通分量。输出 $\sum_{D \in D_F} \sum_{E \in D_F} f(D, E) \pmod{10^9 + 7}$（$1 \le x \le N$）。

输入格式

第一行包含三个整数 $N, M$ 和 $Q$（$2 \le N \le 100\,000, 0 \le M \le N - 1, 1 \le Q \le 100\,000$）。

接下来 $M$ 行，每行包含两个整数 $x$ 和 $y$，表示连接顶点 $x$ 和 $y$ 的边（$1 \le x, y \le N, x \neq y$）。保证给定的图中不存在环。

接下来 $Q$ 行，每行包含一个上述形式的查询。

输出格式

对于每个类型为 3 的查询，输出答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

7 5 5
1 2
1 3
2 4
2 5
3 6
3 1
1 3 7
3 1
2 2 1
3 1

样例输出 1

18
64
21