#include <iostream>
#include <fstream>
#include <ostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

struct City {
    int id, prestige;
    vector<pair<int, int>> neighbors; // pair: neighbor city and cost
};

vector<pair<int, int>> paths;

int main() {
    int n, m;

    // out
    ofstream fout;
    fout.open("taxi.out");

    // in 
    ifstream fin;
    fin.open("taxi.in");
    fin >> n >> m;
    vector<City> cities(n);
    for (int i = 0; i < n; ++i) {
        cities[i].id = i;
        fin >> cities[i].prestige;
    }

    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        paths.push_back({ x, y });
     }

    // prestige permutations
    vector<int> prestige;
    for(int i = 0; i < paths.size(); i++)
    {
        prestige.push_back(cities[i].prestige);
    }
    sort(prestige.begin(), prestige.end());  
    do {  
        
        for(int i = 0; i < m; i++)
        {
             cities[i].prestige = prestige[i];
             cities[i].neighbors.clear();
        }

        // Costs
        for(int i = 0; i < paths.size(); i++)
        {
            pair<int,int> next = paths[i];
            int x = next.first-1; 
            int y = next.second-1; 
            int cost = (cities[x].prestige - cities[y].prestige) * (cities[x].prestige - cities[y].prestige);
            cities[x].neighbors.push_back({ y, cost });
            cities[y].neighbors.push_back({ x, cost });
        }

        // TODO: DFS
        vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
        vector<vector<int>> parent(1 << n, vector<int>(n, -1));

        for (int i = 0; i < n; ++i) {
            dp[1 << i][i] = 0;
        }

        for (int mask = 0; mask < (1 << n); ++mask) {
            for (int u = 0; u < n; ++u) {
                if ((mask & (1 << u)) == 0) continue;

                for (int v = 0; v < n; ++v) {
                    if ((mask & (1 << v)) == 0) {
                        int new_mask = mask | (1 << v);
                        for (const auto& neighbor : cities[u].neighbors) {
                            int neighbor_city = neighbor.first;
                            int cost = neighbor.second;
                            if (new_mask & (1 << neighbor_city)) {
                                if (dp[mask][u] + cost < dp[new_mask][v]) {
                                    dp[new_mask][v] = dp[mask][u] + cost;
                                    parent[new_mask][v] = u;
                                }
                            }
                        }
                    }
                }
            }
        }

        int min_cost = 1e9;
        int last_city = -1;
        int final_mask = (1 << n) - 1;

        for (int i = 0; i < n; ++i) {
            if (dp[final_mask][i] < min_cost) {
                min_cost = dp[final_mask][i];
                last_city = i;
            }
        }

        vector<int> path;
        int current_city = last_city;
        int current_mask = final_mask;

        while (current_mask > 0) {
            int prev_city = parent[current_mask][current_city];
            path.push_back(current_city);
            current_mask ^= (1 << current_city);
            current_city = prev_city;
        }

        reverse(path.begin(), path.end());

        // Output
        for (int i = 0; i < n - 1; ++i) fout << cities[i].prestige << " ";
        fout << cities[n-1].prestige <<  endl;

        // fout << path.size() + 1 << endl; // days
        fout << path.size() << " "; 
        for (int city : path) {
            fout << city + 1 << " "; // +1 for city numbering
        }
        fout << endl << "---" << endl;


    } while(next_permutation(prestige.begin(), prestige.end()));  

    fin.close();
    fout.close();

    return 0;
}