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 different 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.

Task

Your task is to write a program that:

• reads the description of villages and connecting them roads, from the input file pos.in,
• 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,
• writes the result to the output file pos.out.

If there are several possible solutions, your program should output just one of them.

Input

In the first line of the input file pos.in, there are two integers n and m, separated by a single space; n, 1<=n<=200, is the number of villages and m is the number of roads. In each of the following n lines there is one positive integer. The i+1-th line contains w(i), 1<=w(i)<=1 000, specification of the fee paid by the village number i. In each of the following m lines there are two positive integers separated by a single space--villages connected by consecutive roads.

Output

Your program should write one positive integer k, the length of the route, to the first line of the output file pos.out. The following line should contain k+1 numbers of consecutive villages on the route v₁,v₂,...,v_k+1, separated by single spaces, with v₁=v_k+1=1.

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