J. Diameter Pair Sum
time limit per test
5 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

For an unweighted tree $$$T$$$, a simple path $$$P$$$ is a diameter if there is no simple path longer than it. Two paths are different if some vertex is in one path but not the other.

Consider a set of paths $$$D_T$$$ where $$$P \in D_T$$$ if and only if $$$P$$$ is a diameter. Given two paths $$$D$$$ and $$$E$$$, let $$$f(D, E)$$$ be the number of vertices that belong to both $$$D$$$ and $$$E$$$.

You are given an undirected forest (a graph with no cycles) with $$$N$$$ vertices and $$$M$$$ edges. Process $$$Q$$$ queries of the following form:

  • "1 $$$x$$$ $$$y$$$": Connect two vertices $$$x$$$ and $$$y$$$ with an edge ($$$1 \le x, y \le N$$$). It is guaranteed that there is no path between $$$x$$$ and $$$y$$$ at the time of the query.
  • "2 $$$x$$$ $$$y$$$": Remove an edge between two vertices $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le N$$$). It is guaranteed that such an edge exists at the time of the query.
  • "3 $$$x$$$": Let $$$F$$$ be the connected component containing the vertex $$$x$$$. Output the value $$$\sum\limits_{D \in D_F} \sum\limits_{E \in D_F} f(D, E)$$$ modulo $$$10^9 + 7$$$ ($$$1 \le x \le N$$$).
Input

The first line of the input consists of three integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$2 \le N \le 100\,000$$$, $$$0 \le M \le N - 1$$$, $$$1 \le Q \le 100\,000$$$).

Each of the next $$$M$$$ lines consists of two integers $$$x$$$ and $$$y$$$ denoting an edge connecting vertices $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le N$$$, $$$x \neq y$$$). It is guaranteed that there are no cycles in the given graph.

Each of the next $$$Q$$$ lines contains a query in the form described above.

Output

For each query of type 3, output the answer modulo $$$10^9 + 7$$$.

Example
Input
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
Output
18
64
21