MST Game

There is a simple graph G with N vertices and M undirected edges. A simple graph has no self-loop edge (an edge connecting a vertex to itself) and has at most one edge between any two vertices. A spanning tree of a simple graph is a set of edges satisfying the following conditions.

1. The number of edges in the spanning tree is N-1.
2. For any two vertices of the graph, there must be a path connecting them using only edges belonging to the spanning tree.

Among the spanning trees, the one with the minimum sum of edge weights is called a minimum spanning tree (MST).

Now you are going to play the MST game on the graph.

• The MST game is played by removing edges from the graph one at a time and computing the cost of the MST. The cost of an MST is the sum of the weights of its edges. The score of each turn is the cost of the MST found in that turn.
• The process runs for K turns, and in the first turn you must compute the MST cost of the graph given as input.
• After each turn ends, remove the edge with the smallest weight from the MST found in that turn.
• An edge that has been removed once cannot be used in later turns.
• If an MST cannot be formed in some turn, the score of that turn is 0. Naturally, the scores of all later turns are also 0. It is also possible that an MST cannot be formed in the first turn.

Given a simple graph with undirected edges and K, write a program that computes the score of each turn.

The first line gives the number of vertices N, the number of edges M, and the number of turns K. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ min(10,000, N×(N-1)/2), 1 < K ≤ 100)

Then M lines give edge information. Each line consists of the numbers x, y of the two vertices connected by the edge. The same edge is never given more than once. The weights of the edges are 1, 2, ..., M in the order they are given.

Vertices are numbered from 1 to N.

Print K integers on one line separated by spaces. The K integers represent the scores obtained in each turn.

The MST that can be found in the first turn consists of 5 edges {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}, and its cost is 16.

In the second turn, after removing (2, 4), the edge with the smallest cost in the MST found in the first turn, you must find an MST using the remaining edges. However, since no MST exists after removing (2, 4), the score of the second turn and all later turns is 0.