V.I.P.

정점이 $N$개인 완전 그래프 $G$와 활성화 정보 $M$개, 정점의 가중치 $N$개가 주어진다. 처음에는 모든 간선이 비활성화된 간선이다. 활성화 정보는 다음과 같이 주어지며, $M$개의 정보에서 같은 간선이 두 번 이상 활성화되는 경우는 없다.

• $i$ $j$: 정점 $i$와 $j$를 잇는 간선을 활성화된 간선으로 만든다.

가중치가 증가하는 순서대로 방문하는 경로 중 비활성화된 간선을 지나지 않는 경로를 V.I.P.(Very Important Path)라고 한다. 아래 질의가 주어질 때마다 V.I.P.의 개수를 구한다.

• $p\,q$: 정점 $p$와 $q$를 잇는 간선의 활성화 여부를 반대로 바꾼다. 바뀐 그래프의 V.I.P. 개수를 출력한 뒤, 간선의 활성화 여부를 원래대로 되돌린다.

첫 줄에 정점의 개수 $N$, 활성화된 간선의 개수 $M$, 질의의 개수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 10^5; 0 \leq M \leq \min(\frac{N(N-1)}{2}, 2 \times 10^5); 1 \leq Q \leq 10^5)$

둘째 줄에 정점들의 가중치 $w_1, w_2, \ldots, w_N$이 공백으로 구분되어 주어진다. $w_i$는 $i$번 정점의 가중치이다. $(1 \leq w_i \leq 10^9)$

셋째 줄부터 $M + 2$번째 줄까지, $i + 2$번째 줄에 $i$번째 활성화된 간선의 두 끝점 $u_i, v_i$가 공백으로 구분되어 한 줄씩 주어진다. $(1 \leq u_i, v_i \leq N; u_i \neq v_i)$

$M + 3$번째 줄부터 $M + Q + 2$번째 줄까지, $M + i + 2$번째 줄에 $i$번째 질의 $p_i, q_i$가 공백으로 구분되어 한 줄씩 주어진다. $(1 \leq p_i, q_i \leq N; p_i \neq q_i)$

질의가 주어질 때마다 V.I.P.의 개수를 출력한다. 답이 아주 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

그래프 이론에서 경로란 같은 정점을 최대 한 번 방문하는 인접한 정점들의 순서이다. $X(X \geq 1)$개의 정점으로 이루어진 나열 $P = {v_1, v_2, \cdots, v_{X-1}, v_X}$이 경로가 되려면, $i \neq j$일 때 $v_i \neq v_j$이고, $1 \leq i \leq X - 1$에 대해 끝점이 각각 $v_i, v_{i+1}$($v_i \neq v_{i+1}$)인 간선이 존재해야 한다.

증가 수열은 길이가 $n$인 수열 $a$에 대해 $a_1 < a_2 < \cdots < a_{n-1} < a_n$을 만족하는 수열이다.