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 is visited as the different village on the tour and , the village pays euros to the post. However, if , the post agrees to pay 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 villages, numbered from to . 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
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 and , the number of villages and the number of roads.
In each of the following lines, there is one integer. The line contains , the fee paid by the village number .
In each of the following 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 , the length of the route, to the first line of output. The following line should contain space-separated integers — the villages on the route. The route should start and end at the post, thus it must satisfy .
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 | Profit |
---|---|
No interaction | |
No interaction |
The total profit from the table above is . The post pays the postman one euro for each road on the tour, so the final profit is . It can be proven this is the maximum profit for the post.
Comments