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-th \textbfdifferent village on the tour and k<=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. Moreover, the post 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 is placed on the crossing of two roads, on the crossing of four roads, or there is a road going through the village (i.e. there are 2, 4, or 8 roads going out of each village). There can be several roads connecting the same villages or a road can be a loop, i.e. connect a village with itself.
6 7 1 7 4 10 20 5 2 4 1 5 2 1 4 5 3 6 1 6 1 3correct answer in file pos.out
7 1 5 4 2 1 6 3 1