Baltic OI '01 P1 - Postman

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Baltic Olympiad in Informatics: 2002 Day 1, Problem 3

In a 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 though 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 form 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.


1 \le n \le 200

1 \le m \le 1\,000

1 \le w \le 1\,000

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, \ldots, 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
2 4
1 5
2 1
4 5
3 6
1 6
1 3

Sample Output

1 5 4 2 1 6 3 1

Sample Explanation

The villages and roads are shown in the diagram above.

Village\Delta Profit
1w(1) - k = 0
5w(5) - k = +18
4w(4) - k = +7
2w(2) - k = +3
1No interaction
6w(6) - k = 0
3w(3) - k = -2
1No 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.


There are no comments at the moment.