Baltic Olympiad in Informatics: 2002 Day 1, Problem 3

In the countryside a postman has to deliver post to customers that live in villages and along every road connecting the villages.

Your task is to help the postman design a route that goes through every village and every road at least once — the input data are such that this is always possible. However, each route also has a cost. The people in the villages wish that the postman visit their village as early as possible. Therefore, each village has made the following deal with the post: If the village $i$ is visited as the $k^{\text{th}}$ different village on the tour and $k\le w(i)$, the village pays $w(i)-k$ euros to the post. However, if $k>w(i)$, the post agrees to pay $k-w(i)$ euros to the village. If a village is visited again, nothing happens. The post also pays the postman one euro for each road on the tour.

There are $n$ villages, numbered from $1$ to $n$. The post is located in the village number one, so the route should start and end in this village. Each village has access to an even number of road endings.

Your task is to write a program that designs such a route that goes through each village and road at least once and maximizes the total profit (or minimizes the loss) of the post.

Constraints

$1\le n\le 200$

$1\le m\le 1000$

$1\le w\le 1000$

Each village has access to an even number of road endings.

Input Specification

In the first line of input, there are two space-separated integers $n$ and $m$, the number of villages and the number of roads.

In each of the following $n$ lines, there is one integer. The $(i+1{)}^{\text{th}}$ line contains $w(i)$, the fee paid by the village number $i$.

In each of the following $m$ lines there are two space-separated integers — villages connected by a road. There can be several roads connecting the same villages or a road can be a loop, i.e. connect a village with itself.

Output Specification

Your program should write one positive integer $k$, the length of the route, to the first line of output. The following line should contain $k+1$ space-separated integers $v_1,v_2,\dots ,v_{k+1}$ — the villages on the route. The route should start and end at the post, thus it must satisfy $v_1=v_{k+1}=1$.

If there are several possible optimal routes, you may output any one of them.

Sample Input

6 7
1
7
4
10
20
5
2 4
1 5
2 1
4 5
3 6
1 6
1 3

Sample Output

7
1 5 4 2 1 6 3 1

Sample Explanation

The villages and roads are shown in the diagram above.

Village	$\mathrm{\Delta }$ Profit
$1$	$w(1)-k=0$
$5$	$w(5)-k=+18$
$4$	$w(4)-k=+7$
$2$	$w(2)-k=+3$
$1$	No interaction
$6$	$w(6)-k=0$
$3$	$w(3)-k=-2$
$1$	No interaction

The total profit from the table above is $26$. The post pays the postman one euro for each road on the tour, so the final profit is $26-7=19$. It can be proven this is the maximum profit for the post.