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 < ... < a\_{n - 1} < a\_n$을 만족하는 수열이다.