Graph and Queries
You are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an integer value assigned to it at the beginning. You’re also given a sequence of operations and you need to process them as requested. Here’s a list of the possible operations that you might encounter:
- Deletes an edge from the graph.
The format is [D X], where X is an integer from 1 to M, indicating the ID of the edge that you
should delete. It is guaranteed that no edge will be deleted more than once.
- Queries the weight of the vertex with K-th maximum value among all vertexes cur-
rently connected with vertex X (including X itself).
The format is [Q X K], where X is an integer from 1 to N, indicating the id of the vertex, and you may assume that K will always fit into a 32-bit signed integer. In case K is illegal, the value for that query will be considered as undefined, and you should return 0 as the answer to that query.
- Changes the weight of a vertex.
The format is [C X V ], where X is an integer from 1 to N, and V is an integer within the range
[−106, 106].
The operations end with one single character, ‘E’, which indicates that the current case has ended.
For simplicity, you only need to output one real number — the average answer of all queries.
Input
There are multiple test cases in the input file. Each case starts with two integers N and M (1 ≤ N ≤ 2 ∗ 104, 0 ≤ M ≤ 6 ∗ 104), the number of vertexes in the graph. The next N lines describes the initial weight of each vertex (−106 ≤ weight[i] ≤ 106). The next part of each test case describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the graph. It is guaranteed that the number of query operations [Q X K] in each case will be in the range [1, 2 ∗ 105], and there will be no more than 2 ∗ 105 operations that change the values of the vertexes [C X V ].
There will be a blank line between two successive cases. A case with N = 0, M = 0 indicates the end of the input file and this case should not be processed by your program.
Output
For each test case, output one real number — the average answer of all queries, in the format as indicated in the sample output. Please note that the result is rounded to six decimal places.
Explanation for samples:
For the first sample:
D 3 – deletes the 3rd edge in the graph (the remaining edges are (1, 2) and (2, 3))
Q 1 2 – finds the vertex with the second largest value among all vertexes connected with 1. The
answer is 20.
Q 2 1 – finds the vertex with the largest value among all vertexes connected with 2. The answer is
2/2
D 2 – deletes the 2nd edge in the graph (the only edge left after this operation is (1, 2))
Q 3 2 – finds the vertex with the second largest value among all vertexes connected with 3. The answer is 0 (Undefined).
C 1 50 – changes the value of vertex 1 to 50.
Q 1 1 – finds the vertex with the largest value among all vertex connected with 1. The answer is 50. E – This is the end of the current test case. Four queries have been evaluated, and the answer to
this case is (20 + 30 + 0 + 50) / 4 = 25.000.
For the second sample, caution about the vertex with same weight: Q 1 1 – the answer is 20
Q 1 2 – the answer is 20
Q 1 3 – the answer is 10
Sample Input
33
10
20
30
12 23 13 D3 Q12 Q21 D2 Q32 C 1 50 Q11 E
33 10
20
20 12 23 13 Q11 Q12 Q13 E
00
Sample Output
Case 1: 25.000000
Case 2: 16.666667