#631 Dismantling

Statement

Statement language

You are given a connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$ , and the edges are numbered from $1$ to $M$ in input order. Vertex $i$ has weight $W_i$ . The graph has no self-loops and no multiple edges between the same pair of vertices.

Remove all edges by performing the following operation exactly $M$ times.

Choose and remove one edge that is still present. Let its endpoints be $u$ and $v$ .
Check whether a path from $u$ to $v$ exists using the edges remaining immediately after the removal.

If such a path exists, the cost is $\min(W_u,W_v)$ .
Otherwise, the cost is $\max(W_u,W_v)$ . In this case, one connected component splits into two.

Find the minimum total cost of removing all edges and an edge removal order that achieves it.

Input

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the following two lines in input order.

On the first line, print the minimum total cost of removing all edges.
On the second line, print $M$ edge numbers describing a removal order that achieves that cost. Each number from $1$ to $M$ must appear exactly once.

If there are multiple optimal removal orders, print any of them.

Constraints

$1\leq T\leq100\,000$ .
$2\leq N\leq200\,000$ .
$N - 1$ .

Subtasks

#	Score	Constraints
1	11	$N\leq5$ . $M\leq7$ . The sum of $N$ over all test cases is at most $200$ .

Samples

Sample 1

Input

Output

For the first test case, remove the edges as follows.

Remove edge $1$ , joining vertices $1$ and $3$ . The path $1\to2\to3$ remains, so the cost is .