My First Little Graph
By Giovanna Kobus Conrado, Universidade de São Paulo 
Brazil
By Giovanna Kobus Conrado, Universidade de São Paulo Brazil
Happy Birthday! As a birthday gift, your mother made your biggest dream come true and gave you a little pet graph. It's breed is very rare: it has n vertices and each one of them has a value. Initially the vertice i has value i ( 1<= i <= n) and for each pair of vertices the is an edge connecting them with weight equal to the magnitude of the difference of their values.
You little graph is in its development stage, that means that the value of vertice i can change to k at any time! Besides that, graphs eat a lot and you must feed them daily with an amount of food equal to the weight of their maximum spanning tree.
Write a program to take good care of your graph, or your mother might take it from you!
Note: The maximum spanning tree of a graph is the tree which vertices are vertices of the original graph and edges are edges of the original graph that has the maximum sum of weight of it's edges.
The first line of input is an integer t (t<=10): the number of test cases.
Each case starts with an integer N (0<=N<=2*105): the number of vertices of the graph.
The next line will be an integer Q (1<=Q<=2*105) : the number of instructions to be followed.
An instruction can be of the following types:
1 i k : the value of vertice i (1 <= i , k <= n) changes to k ( the edges connected to it must change accordingly).
2 : the weight of the maximum spanning tree of your graph.
For each instruction of the type 2, print the weight of the maximum spanning tree of the graph.
| Input Sample | Output Sample |
|
1 5 3 2 1 3 5 2 |
12 14 |