트리와 2개의 지름

문제

이메이미 교수의 알고리즘 과목을 재수강하게 된 메시는 작년과 같은 실수를 반복하지 않기 위해 중간고사를 철저히 대비하려고 한다. 작년에 가중치 없는 트리의 지름에 관련된 문제가 나왔던 것을 참고하여, 메시는 다음과 같은 문제를 스스로 고안해내었다.

"가중치 없는 트리 $T$에 대해, 두 정점을 잇는 최단경로 중 가장 긴 것들을 $T$의 지름이라고 한다. $T$의 지름들의 모임을 $\mathcal{D}_{T}$라고 하자. $T$의 두 지름 $D, E \in \mathcal{D}_{T}$에 대해 (둘은 같을 수 있다), 둘 모두에 공통으로 속하는 정점의 개수를 $f(D, E)$라 하자. 가능한 모든 $D, E$에 대한 $f(D, E)$의 합 $F(T) = \sum_{D \in \mathcal{D}} \sum_{E \in \mathcal{D}} f(D, E)$를 구하여라."

$N$개의 정점을 가진 트리에는 최대 $O(N^2)$개의 지름이 있기 때문에, 메시는 모든 지름을 구해서 각각이 공통으로 소유하는 정점 개수를 구하는 방식으로 훌륭한 $O(N^5)$ 코드를 구현해냈다. 이 정도라면 아무리 어려운 이메이미 교수의 시험이라도 통과할 수 있을 것만 같았다.

하지만 작년 시험에서 메시를 좌절시켰던 것은 무수한 양의 쿼리였기 때문에, 심기일전한 메시는 쿼리에 대한 대비도 미리 하고자 한다. 간선을 연결하거나 제거하는 쿼리를 추가하기 위해, 맨 처음에 주어지는 그래프를 트리가 아니라 포레스트로 바꿨다. 즉, 그래프에 여러 개의 연결 컴포넌트가 있을 수도 있다.

쿼리는 다음 중 하나로, 총 $Q$개 주어진다.

$1$ $x$ $y$ : 정점 $x$와 $y$를 연결한다. 이 쿼리가 들어올 때 정점 $x$와 $y$는 서로 다른 연결 컴포넌트에 있다.

$2$ $x$ $y$ : 정점 $x$와 $y$를 연결하는 간선을 제거한다. 이 쿼리가 들어오기 전에 정점 $x$와 $y$를 연결하는 간선이 존재한다.

$3$ $x$ : 정점 $x$가 포함되는 트리 $T$에 대해 $F(T)$를 $10^9+7$로 나눈 나머지를 출력한다. 이 쿼리가 들어오기 전에 정점 $x$가 포함된 연결 컴포넌트에는 정점이 2개 이상 존재한다.

메시는 훌륭한 $O(QN^{5})$ 코드를 완성한 뒤 당신에게 검수를 부탁했다. 이 문제를 풀고 큰 데이터를 추가해서 메시가 중간고사를 잘 볼 수 있도록 도와주자.

입력

입력의 첫 줄에 정점의 개수 $N$, 간선의 개수 $M$, 쿼리의 개수 $Q$가 주어진다.

다음 $M$줄에는 초기 상태의 간선이 연결하는 두 정점의 번호 $x, y$가 주어진다. 정점의 번호는 $1$번부터 $N$번까지이다.

다음 $Q$줄에는 각 쿼리를 나타내는 정보가 주어진다.

출력

$3$번 쿼리가 들어올 때마다 $F(T)$를 $10^9+7$로 나눈 나머지를 출력한다.

제한

• $2 \le N \le 100\,000$

• $0 \le M \le N - 1$

• 입력으로 주어지는 그래프는 포레스트이다.

• $1 \le Q \le 100\,000$

• $3$번 쿼리가 하나 이상 존재한다.

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

18
64
21

출처

• 문제를 만든 사람: imeimi2000