I postman has to deliver post to villagers who live in several villages and in the roads that connect the villages. Actually there are houses in villages as well as along the sides of the roads. There are n villages and m roads. Villages are numbered from 1 to n, and all the villages are connected by some paths. A path consists of some connected roads. The postman starts his journey from village 1 and he must finish his journey at village 1. So, he wants to find a tour that visits each village, each road at least once. Since all the villagers want the postman to come in their house as early as possible; they designed a cost service.

If an unvisited village i is visited as the k^th (1 indexed) different village on the tour and k ≤ w(i), the village pays w(i) - k taka to the post. However, if k > w(i), the post agrees to pay k - w(i) taka to the village. Moreover, the post has to spend one taka for each road the postman visits. Even if the postman travels a road p times, then the post has to spend p taka. The villages are established in a way that such a tour is always possible. And there are always 2, 4 or 8 roads going out from each village. Now your task is to help the post to find a route that maximizes the earning (or minimizes the loss).

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 200) and m. The next line contains n space separated integers. The i^th integer denotes the w(i) for the i^th village (0 ≤ w(i) ≤ 1000). Each of the next m lines contains two integers u v (1 ≤ u, v ≤ n) denoting that there is a road between village u and v. You can assume that the given input follows the constraints given above.

For each case, print the case number and the maximum profit. Then in the next line print the route. So, this line should contain numbers of consecutive villages on the route v₁ v₂ ... v_x separated by single spaces, with v₁ = v_x = 1. There can be several solutions, any valid one will do.

This is a special judge problem, wrong output format may cause 'wrong answer'.