27E. Chopsticks

2750 pts3s256 MB

You have $n$ chopsticks, numbered from $1$ to $n$ . Initially, chopstick $i$ has length $a_i$ .

There are $m$ pieces of sushi, numbered from $1$ to $m$ . Sushi $j$ must be eaten using chopsticks $u_j$ and $v_j$ .

When you eat a piece of sushi, compare the current lengths of its two chopsticks. If they differ, shorten the longer chopstick until the two lengths are equal. If they are equal, neither chopstick is changed.

Each chopstick may be used any number of times, but it may be shortened at most once in total.

Find an order in which to eat all the sushi that minimizes the total length removed from the chopsticks. Output this minimum total and one optimal order. If several optimal orders exist, output any of them.

Different pieces of sushi may require the same pair of chopsticks. A valid order always exists.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le m \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$1 \le u_j, v_j \le n$
$u_j \ne v_j$
The sums of $n$ and $m$ over all test cases do not exceed $2 \times 10^5$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

Output

For each test case, print the minimum total length removed as $\mathrm{answer}$ on the first line. On the second line, print a permutation $p_1, p_2, \ldots, p_m$ of $1,2,\ldots,m$ , where sushi $p_i$ is eaten on turn $i$ . This order must attain the printed minimum and shorten each chopstick at most once. If several optimal orders exist, print any of them.

\left. \begin{array}{l} \mathrm{answer} \\ p_1 \quad p_2 \quad \cdots \quad p_m \end{array} \right\} \times t

Samples

Input

Case 1

2 1
5 5
1 2

Case 2

Explanation

Case 1

The two chopsticks already have equal lengths, so nothing is removed.

Case 2

Eating sushi 1 shortens chopstick 1 from 9 to 6. Eating sushi 2 then shortens chopstick 2 from 6 to 2. The total removed length is 3 + 4 = 7.

Output

Case 1

0
1

Case 2

7
1 2

Input

Case 1

Case 2

Case 3

Explanation

Case 1

Eating sushi 2 first shortens chopstick 1 from 9 to 2. Sushi 1 then shortens chopstick 2 from 6 to 2, removing 11 units in total. The opposite order would shorten chopstick 1 twice and is not allowed.

Case 2

Eating sushi 1 changes nothing. Sushi 2 then shortens chopstick 1 from 8 to 3. Only 5 units are removed, which is unavoidable when eating sushi 2.

Case 3

Sushi 4 changes nothing. The remaining sushi in the shown order shorten chopsticks 2, 1, 3, and 5 to length 3, removing 6, 9, 3, and 3 units, respectively. Every chopstick is shortened at most once, and the minimum total removed length is 21.

Output

Case 1

11
2 1

Case 2

5
1 2

Case 3

21
4 3 1 2 5

You have $n$ chopsticks, numbered from $1$ to $n$ . Initially, chopstick $i$ has length $a_i$ .

There are $m$ pieces of sushi, numbered from $1$ to $m$ . Sushi $j$ must be eaten using chopsticks $u_j$ and $v_j$ .

Each chopstick may be used any number of times, but it may be shortened at most once in total.

Different pieces of sushi may require the same pair of chopsticks. A valid order always exists.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le m \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$1 \le u_j, v_j \le n$
$u_j \ne v_j$
The sums of $n$ and $m$ over all test cases do not exceed $2 \times 10^5$ .

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \\ p_1 \quad p_2 \quad \cdots \quad p_m \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

27E. Chopsticks

Constraints

Input

Output

Samples

27E. Chopsticks

Constraints

Input

Output

Samples