On vacation in the Warm Country, Vera met a handsome volleyball tractor driver Peter. Tourist Peter, by the way, is going after a great holiday in the Warm Country to go on a trip to the cities of Europe. As is known, Europe has a developed transport system: in Europe there are V cities of interest to Peter and E routes of night trains. Each route connects two different cities, the travel time is one night. Trains run in both directions along the route.
The main purpose of Peter's trip is to see local attractions. Since Peter — an incredibly busy man, he decided that the entire journey should take no more than four days. Peter has already seen a lot, so Peter spends exactly one day on sightseeing in each city. He wants to make the most practical tour: every day he will spend on exploring the city, and every night — to travel by night train between cities. Of course, Peter has no desire to visit the same city several times.
But Peter's pragmatism does not end there: Peter, like a real tourist, wants to see the most beautiful European sights. He studied directories for a long time and for each city estimated his expected joy from his visit pi. Now he wants to find a route where his joy will be the greatest. Help Peter find such a route.
Input file format
The first line of the input contains two integers V and E (1 <= V, E <= 3 · 10
5 ) — the number of cities and train routes, respectively. The next line contains V integers p
i (1 <= p
i <= 10
8 ), where pi denotes the expected joy from visiting the city with number i. The following E lines contain descriptions of train routes. Each description consists of a pair of different numbers ai and bi (1 <= a
i, b
i <= V ) — numbers of cities between which this train route runs. It is guaranteed that there is at most one train route between each pair of cities.
Output file format
In the first line of output print the number K (1 <= K <= 4) — the number of cities in the optimal route of the tourist Petra. On the next line print the numbers of these cities in the order they were visited. Cities are numbered starting from one. If there are several optimal routes, print any of them.
|
Enter |
Output |
5 4
4 2 3 1 5
1 2
23
34
4 5 |
4
2 3 4 5
|
4 3
1 2 3 4
1 2
1 3
14 |
3
4 1 3
|