31795번 - 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$을 만족하는 수열이다.