#include<bits/stdc++.h>

#define MAXN 15
#define INF 100001


using namespace std;
using namespace std::chrono;

int n, m;
struct state
{
    int8_t parent;
    bool flag;
};
state mini(state &a, state b)
{
    if(a.parent != -1) return a;
    return b;
}
state dp[MAXN][2 * MAXN][1<<14];
mt19937 mt(time(nullptr));
bool vis[INF];
int last, promen;
long long ansLarge = 1e18, purvoto;

vector<int> M[INF], pathLarge, weights;

int randomfunc(int j)
{
    return mt() % j;
}
class solveSmall
{
public:

    int a, b, podredba[MAXN], promen;
    bool flag, adj[1024][1024];
    vector<int> path;
    void printPath(int v, int turn, int mask)
    {
        while(turn)
        {
            //cout<<v<<" "<<turn<<" "<<mask<<"       ";
            path.push_back(v);
            int parv = (int)dp[v][turn][mask].parent;
            //cout<<parv<<endl;
            if(parv == -1 || v == -1) return;
            if(dp[v][turn][mask].flag == false) mask = mask ^ (1 << v);
            v = parv;
            turn --;
        }
        path.push_back((int)dp[v][turn][mask].parent);
        //cout<<(int)dp[v][turn][mask].parent<<endl;

    }
    void read()
    {
        for(int i = 0; i < n; i ++)
        {
            int w;
            cin>>w;
            weights.push_back(w);
        }
        int a, b;
        for(int i = 0; i < m; i ++)
        {
            cin>>a>>b;
            adj[a - 1][b - 1] = adj[b - 1][a - 1] = true;
        }
    }
    pair<int, int> mul()
    {
        for(int mask = 0; mask < (1 << n); mask ++)
        {
            for(int turn = 1; turn < 2 * n; turn ++)
            {
                for(int v = 0; v < n; v ++)
                {
                    dp[v][turn][mask] = {-1, 0};
                }
            }
        }
        for(int v = 0; v < n; v ++)
        {
            int mask = (1 << v);
            dp[v][1][mask] = {v, 0};
        }

        for(int mask = 1; mask < (1 << n); mask ++)
        {
            for(int turn = 2; turn < 2 * n; turn ++)
            {
                for(int v = 0; v < n; v ++)
                {
                    if((1 << v) & mask)
                    {
                        int prevMask = mask ^ (1 << v);
                        for(int u = 0; u < n; u ++)
                        {
                            if(!adj[u][v] || u == v) continue;
                            if((mask & (1 << u)) && (dp[u][turn - 1][mask].parent != -1)) dp[v][turn][mask] = mini(dp[v][turn][mask], {u, true});
                            if((prevMask & (1 << u)) && (dp[u][turn - 1][prevMask].parent != -1)) dp[v][turn][mask] = mini(dp[v][turn][mask], {u, false});
                        }
                        if(mask == (1 << n) - 1 && dp[v][turn][mask].parent != -1) return {v, turn};
                    }
                }
            }
        }
        return {0, 0};
    }
    int solve()
    {
        bool occ[1024];
        for(int i = 0; i < 1024; i ++) occ[i] = false;
        int ind = 0;
        for(int i = 0; i < path.size(); i ++)
        {
            //cout<<path[i]<<" ";
            if(!occ[path[i]])
            {
                occ[path[i]] = true;
                podredba[path[i]] = weights[ind ++];
            }
        }
        //cout<<endl;
        int sum = 0;
        for(int i = 0; i < path.size(); i ++)
        {
            if(i) sum += (podredba[path[i]] - podredba[path[i - 1]]) * (podredba[path[i]] - podredba[path[i - 1]]);
        }
        return sum;
    }
    void print1()
    {
        int lastelement = -1;
        bool occ[MAXN];
        memset(occ, 0, MAXN);
        //cout<<"111111111\n";
        //for(int i = 0; i <= n; i ++) cout<<podredba[i]<<endl;
        for(int i = n - 1; i > -1; i --) cout<<podredba[i]<<" ";
        cout<<endl;
        cout<<promen<<endl;
        vector<int> cur;
        for(int i = path.size() - 1; i > -1; i --)
        {
            if(!occ[path[i]])
            {
                occ[path[i]] = 1;
                cur.push_back(path[i]);
            }
            else if(cur.size())
            {
                if(lastelement != -1) cout<<cur.size() + 1<<" "<<lastelement<<" ";
                else cout<<cur.size()<<" ";
                for(auto item : cur)
                {
                    cout<<item + 1<<" ";
                    lastelement = item + 1;
                }
                cout<<endl;
                cur.clear();
                cur.push_back(path[i]);
            }
        }
        /*if(lastelement != -1) cout<<cur.size() + 1<<" "<<lastelement<<" ";
        else cout<<cur.size()<<" ";
        for(auto item : cur)
        {
            cout<<item + 1<<" ";
            lastelement = item + 1;
        }
        cout<<endl;*/
    }
    void print2()
    {
        int lastelement = -1;
        bool occ[MAXN];
        memset(occ, 0, MAXN);
        for(int i = 0; i < n; i ++) cout<<podredba[i]<<" ";
        cout<<endl;
        cout<<promen<<endl;
        vector<int> cur;
        for(int i = 0; i < path.size(); i ++)
        {
            if(!occ[path[i]])
            {
                occ[path[i]] = 1;
                cur.push_back(path[i]);
            }
            else if(cur.size())
            {
                if(lastelement != -1) cout<<cur.size() + 1<<" "<<lastelement<<" ";
                else cout<<cur.size()<<" ";
                for(auto item : cur)
                {
                    cout<<item + 1<<" ";
                    lastelement = item + 1;
                }
                cout<<endl;
                cur.clear();
                cur.push_back(path[i]);
            }
        }
        /*if(lastelement != -1) cout<<cur.size() + 1<<" "<<lastelement<<" ";
        else cout<<cur.size()<<" ";
        for(auto item : cur)
        {
            cout<<item + 1<<" ";
            lastelement = item + 1;
        }
        cout<<endl;  */
    }
    void mainSmall()
    {
        read();
        pair<int, int> ret = mul();
        if(ret.second == 0) return;
        promen = ret.second - n + 1;
        sort(weights.begin(), weights.end());
        printPath(ret.first, ret.second, (1 << n) - 1);
        int case1 = solve();
        reverse(weights.begin(), weights.end());
        int case2 = solve();
        if(case1 < case2)
        {
            print1();
        }
        else print2();

    }
};
vector<int> finalPath;
long long finalPodredba[INF], podreddba[INF];

class solveBig
{
public:
    void dfs(int v)
    {
        vis[v] = 1;
        last = v;
        pathLarge.emplace_back(v);
        for(auto &to : M[v])
        {
            if(!vis[to])
            {
                dfs(to);
                pathLarge.emplace_back(v);
            }
        }
    }
    void removeExcess()
    {
        while(pathLarge.size() && pathLarge[pathLarge.size() - 1] != last) pathLarge.pop_back();
    }
    long long calc(long long podredba[])
    {
        long long ind = 0, ret = 0;
        fill_n(podredba, n + 1, -1);
        unordered_map<int, int> occu;
        int K = 1;
        for(int i = 0; i < pathLarge.size(); i ++)
        {
            occu[pathLarge[i]] ++;
            if(occu[pathLarge[i]]) K ++;
            if(podredba[pathLarge[i]] == -1)
            {
                podredba[pathLarge[i]] = weights[ind ++];

            }
            if(i)
            {
                ret += (podredba[pathLarge[i]] - podredba[pathLarge[i - 1]]) * (podredba[pathLarge[i]] - podredba[pathLarge[i - 1]]);
                if(ret * K > 1e17) return 1e18 - 1;
            }

        }
        return K * ret;
    }
    void analiz(vector<int> &prekusvane)
    {
        for(int i = 0; i < finalPath.size(); i ++)
        {
            if(!vis[finalPath[i]])
            {
                vis[finalPath[i]] = true;
            }
            else
            {
                memset(vis, 0, n + 1);
                vis[finalPath[i]] = true;
                purvoto ++;
                prekusvane.emplace_back(i);
            }
        }
    }
    void solveLarge()
    {
        auto start = high_resolution_clock::now();
        for(int i = 0; i < n; i ++)
        {
            int w;
            cin>>w;
            weights.emplace_back(w);
        }
        sort(weights.begin(), weights.end());
        int a, b;
        for(int i = 0; i < m; i ++)
        {
            cin>>a>>b;
            M[a].push_back(b);
            M[b].push_back(a);
        }
        vector<int> prekusvane;
        for(int i = 1; i <= n; i ++) finalPodredba[i] = weights[i - 1];
        for(int ti = 0; ti < 10000; ti ++)
        {
            last = 0;
            for(int i = 1; i <= n; i ++)
            {
                memset(vis, 0, n + 1);
                pathLarge.clear();
                for(int j = 1; j <= n; j ++)
                {
                    random_shuffle(M[j].begin(), M[j].end(), randomfunc);
                }
                dfs(i);
                removeExcess();
                long long current = calc(podreddba);
                if(current < ansLarge)
                {
                    ansLarge = current;
                    finalPath = pathLarge;
                    for(int i = 1; i <= n; i ++) finalPodredba[i] = podreddba[i];
                }
                auto krai = high_resolution_clock::now();
                auto duration = duration_cast<microseconds>(krai - start);
                if(duration.count() > 3300000) break;
            }
        }
        memset(vis, 0, n + 1);
        analiz(prekusvane);
        for(int i = 1; i <= n; i ++) cout<<finalPodredba[i]<<" ";
        cout<<endl<<purvoto + 1<<endl;
        int lasted = 0;
        for(int i = 0; i < prekusvane.size(); i ++)
        {
            if(!i) cout<<prekusvane[i] - lasted<<" ";
            else cout<<prekusvane[i] - lasted + 1<<" "<<finalPath[lasted - 1]<<" ";
            for(int j = lasted; j < prekusvane[i]; j ++) cout<<finalPath[j]<<" ";
            lasted = prekusvane[i];
            cout<<'\n';
        }
        prekusvane.emplace_back(finalPath.size());
        if(lasted)cout<<finalPath.size() - lasted + 1<<" ";
        else cout<<finalPath.size() - lasted<<" ";
        if(lasted) cout<<finalPath[lasted - 1]<<" ";
        for(int j = lasted; j < finalPath.size(); j ++) cout<<finalPath[j]<<" ";
    }
};
int main()
{
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    if(n < 15 && n != 11)
    {
        solveSmall inst;
        inst.mainSmall();
    }
    else
    {
        solveBig inst2;
        inst2.solveLarge();

    }
    return 0;
}
/*
15 20
2 8 4 5 3 7 10 2 0 5 16 17 19 20 1
1 12
2 6
3 7
5 2
9 7
9 1
7 4
6 3
3 2
6 7
8 7
8 3
8 5
3 7
1 9
14 13
15 12
3 11
14 2
10 7

15 25
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61
1 6
2 9
2 11
3 13
3 5
4 8
4 10
5 11
5 9
6 3
7 12
7 3
7 5
8 7
8 3
10 3
10 9
12 11
12 9
13 4
14 3
14 2
14 12
15 7
15 8
0 61 24 78 64 5 41 27 67 69 62 45 81 58 34
1
16 268494360 1 6 3 8 15 7 12 14 2 11 5 9 10 4 13
*/