CF1789C.Serval and Toxel's Arrays

Toxel likes arrays. Before traveling to the Paldea region, Serval gave him an array $a$ as a gift. This array has $n$ pairwise distinct elements.

In order to get more arrays, Toxel performed $m$ operations with the initial array. In the $i$-th operation, he modified the $p_{i}$-th element of the $(i-1)$-th array to $v_{i}$, resulting in the $i$-th array (the initial array $a$ is numbered as $0$). During modifications, Toxel guaranteed that the elements of each array are still pairwise distinct after each operation.

Finally, Toxel got $m+1$ arrays and denoted them as $A_{0}=a, A_{1},\ldots,A_{m}$. For each pair $(i,j)$ ($0\le i \lt j\le m$), Toxel defines its value as the number of distinct elements of the concatenation of $A_{i}$ and $A_{j}$. Now Toxel wonders, what is the sum of the values of all pairs? Please help him to calculate the answer.

Toxel 喜欢数组。在前往帕底亚地区之前，Serval 送给他一个数组 $a$ 作为礼物。该数组包含 $n$ 个两两互异的元素。

为了得到更多数组，Toxel 对初始数组执行了 $m$ 次操作。在第 $i$ 次操作中，他将第 $(i-1)$ 个数组的第 $p_{i}$ 个元素修改为 $v_{i}$，从而得到第 $i$ 个数组（初始数组 $a$ 编号为 $0$）。在每次修改过程中，Toxel 保证每个数组的所有元素在操作后仍保持两两互异。

最终，Toxel 得到了 $m+1$ 个数组，并将它们记为 $A_{0}=a, A_{1},\ldots,A_{m}$。对于每一对 $(i,j)$（其中 $0\le i \lt j\le m$），Toxel 将其值定义为数组 $A_{i}$ 与 $A_{j}$ 的拼接所得数组中不同元素的个数。现在 Toxel 想知道：所有这样的数对 $(i,j)$ 的值之和是多少？请帮助他计算该答案。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le10^{4}$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le n,m\le2\cdot10^{5}$) — the length of the array and the number of operations.

The second line of each test case contains $n$ integers $a_{1},a_{2},\dots,a_{n}$ ($1\le a_{i}\le n+m$). It is guaranteed that all $a_i$ are pairwise distinct.

Each of the next $m$ lines of each test case contains two integers $p_{i}$ and $v_{i}$ ($1\le p_{i}\le n$, $1\le v_{i}\le n+m$) — the position of the modified element and its new value. It is guaranteed that the elements of each array are still pairwise distinct after each modification.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2\cdot10^{5}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1\le t\le10^{4}$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le2\cdot10^{5}$）—— 分别表示数组的长度和操作次数。

每个测试用例的第二行包含 $n$ 个整数 $a_{1},a_{2},\dots,a_{n}$（$1\le a_{i}\le n+m$）。保证所有 $a_i$ 两两不同。

每个测试用例接下来的 $m$ 行中，每行包含两个整数 $p_{i}$ 和 $v_{i}$（$1\le p_{i}\le n$, $1\le v_{i}\le n+m$）—— 分别表示被修改元素的位置及其新值。保证每次修改后，数组中的所有元素仍两两不同。

保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $2\cdot10^{5}$。

For each test case, print a single integer — the sum of the values of all pairs of arrays.

对于每个测试用例，输出一个整数——所有数组对的值之和。

In the first test case, the arrays change as follows: $[1,2,3]\to[\underline{4},2,3]\to[4,\underline{5},3]$.

The concatenation of the $0$-th array and the $1$-st array is \require{cancel}[1,2,3,4,\cancel{2},\cancel{3}]. There are $4$ distinct elements.

The concatenation of the $0$-th array and the $2$-nd array is \require{cancel}[1,2,3,4,5,\cancel{3}]. There are $5$ distinct elements.

The concatenation of the $1$-st array and the $2$-nd array is \require{cancel}[4,2,3,\cancel{4},5,\cancel{3}]. There are $4$ distinct elements.

Strikethrough elements are duplicates in the array.

Therefore, the answer is $4+5+4=13$.

In the second test case, note that the array may remain unchanged after operations.

在第一个测试用例中，数组的变化过程如下：$[1,2,3]\to[\underline{4},2,3]\to[4,\underline{5},3]$。

第 $0$ 个数组与第 $1$ 个数组的拼接结果为 \require{cancel}[1,2,3,4,\cancel{2},\cancel{3}]，其中包含 $4$ 个不同的元素。

第 $0$ 个数组与第 $2$ 个数组的拼接结果为 \require{cancel}[1,2,3,4,5,\cancel{3}]，其中包含 $5$ 个不同的元素。

第 $1$ 个数组与第 $2$ 个数组的拼接结果为 \require{cancel}[4,2,3,\cancel{4},5,\cancel{3}]，其中包含 $4$ 个不同的元素。

被删除线标记的元素表示该元素在拼接后的数组中重复出现。

因此，答案为 $4+5+4=13$。

在第二个测试用例中，请注意：数组在执行操作后可能保持不变。