Problem Description

Normally, programming languages make one of the following choices when managing memory:

• Let users manage memory manually (C, C++, Rust, etc.). This usually gives good performance, but also places a heavy programming burden on users.
• Use a garbage collection system (Java, Go, etc.). This requires maintaining a runtime system, and it introduces many unpredictable costs in memory usage and program performance.

Despite many issues, the most widely used automatic memory management approach is still the Tracing Garbage Collector. The basic idea is to maintain reference relationships between objects to form a graph. Each time collection happens, it scans the reference graph to deduce which objects can no longer be reached, and frees the memory they occupy. The biggest problem with this traditional approach is that maintaining reference chains is expensive, and as the number of maintained objects increases, the scanning cost also increases.

Little L is a girl who likes thinking. She found that maintaining a Garbage Collector is very complicated, so she decided to consider a simpler model (note that it may be completely different from any real-world GC rules!).

You are given an undirected graph with $n$ vertices and $m$ edges, with no multiple edges or self-loops. Vertices and edges are both numbered starting from $1$. Each vertex represents an object that occupies some amount of memory, and each edge corresponds to a reference relationship (note that the reference relationship here is undirected). The program starts running at time $0$ and ends at time $q + 1$. For each time $i = 1, 2, 3, \dots, q$, exactly one of the following two operations happens:

• DELETE $i$: delete the edge $(x_i, y_i)$, and it is guaranteed that you will not delete an edge that has already been deleted.
• GC: perform one garbage collection, i.e., kill all vertices that are not reachable from the start vertex, and free the memory they occupy. (Note that deleting vertices here does not delete the edges connected to these vertices.)

You may assume that these operations are completed instantly. After all operations are done, i.e., at time $q + 1$, the program ends and deletes all remaining vertices (including vertex $1$).

The memory occupied by vertex $i$ is $a_i$. You need to compute $\sum_{i = 1}^{n} a_i \cdot \mathit{alive}_i$, where $\mathit{alive}_i$ is the time that vertex $i$ stays alive. At time $0$, all vertices are alive.

Input Format

The first line contains three positive integers $n, m, q$, representing the number of objects, the number of reference relationships, and the number of operations.

The next $m$ lines each contain two positive integers $x_i, y_i$, describing the two endpoints of the $i$-th reference relationship.

The next $q$ lines are each in one of the following two forms. The $i$-th line describes the operation at time $i$:

• The string DELETE and a positive integer $x$, with the meaning described in Description.
• The string GC, with the meaning described in Description.

The next line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the memory size occupied by each object.

Output Format

Output one line with one integer, the answer as described in Description.

6 6 8
1 2
2 3
2 4
1 4
2 5
1 6
GC
DELETE 5
DELETE 3
GC
DELETE 1
GC
DELETE 2
GC
1 2 3 4 5 6

149

样例 2 见附件 garbage2.in
本组数据满足测试点 6 的限制。

样例 2 见附件 garbage2.ans

样例 3 见附件 garbage3.in
本组数据满足测试点 11 的限制。

样例 3 见附件 garbage3.ans

Hint

Sample 1 Explanation

At time $4$, vertex $5$ is deleted.

At time $6$, vertices $2, 3$ are deleted.

At time $9$, vertices $1, 4, 6$ are deleted.

So the answer is $5 \times 4 + (2 + 3) \times 6 + (1 + 4 + 6) \times 9 = 20 + 30 + 99 = 149$.

Constraints

For all testdata, $1 \leq n, m, q \leq 4 \times 10^5$, $1 \leq a_i \leq 10^8$.

The detailed constraints are shown in the table below.

Translated by ChatGPT 5