#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <ctime>

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, m;
llong s[MAXN];
int par[MAXN];
int ansSZ[MAXN];
int ansPar[MAXN];
llong price[MAXN];
std::mt19937 rng(69420);
std::vector <int> g[MAXN];
std::vector <int> t[MAXN];
std::vector <int> chain, ansChain;
double begTime, endTime;
bool vis[MAXN];
int sz[MAXN];

void dfsS(int node, int p, int l, int r)
{
    chain.push_back(node);
    if (l == r)
    {
        price[node] = s[l];
        return;
    }

    std::vector <std::pair <int,int>> sizes;
    for (const int &u : t[node])
    {
        if (u != p)
        {
            sizes.push_back({u, sz[u]});
        }
    }

    std::shuffle(sizes.begin(), sizes.end(), rng);
    int which = sizes.size() / 2;
    int sum = l;
    int cnt = 0;

    for (const auto &[u, size] : sizes)
    {
        if (cnt == which)
        {
            price[node] = s[sum];
            sum++;
        }

        dfsS(u, node, sum, sum + size - 1);
        chain.push_back(node);
        sum += size;
        cnt++;
    }
}

void dfs(int node, int p)
{
    sz[node] = 1;
    vis[node] = true;
    for (const int &u : g[node])
    {
        if (vis[u])
        {
            continue;
        }

        t[node].push_back(u);
        t[u].push_back(node);
        dfs(u, node);
        sz[node] += sz[u];
    }
}

void dfsSZ(int node, int p)
{
    sz[node] = 1;
    par[node] = p;
    for (const int &u : t[node])
    {
        if (u == p)
        {
            continue;
        }

        dfsSZ(u, node);
        sz[node] += sz[u];
    }
}

llong calcCost()
{
    int k = 1;
    int ptr = 1;
    int last = -1;
    llong res = 0;
    for (const int &u : chain)
    {
        if (last != -1)
        {
            res += (price[u] - price[last]) * (price[u] - price[last]);
            if (sz[u] == 1)
            {
                k++;
            }
        }

        last = u;
    }

    return k * res;
}

void solve()
{
    std::sort(s + 1, s + 1 + n);
    llong mySol = INF + 1;
    while (true)
    {
        endTime = clock();
        // std::cout << (endTime - begTime) / CLOCKS_PER_SEC << '\n' << std::flush;
        if ((endTime - begTime) / CLOCKS_PER_SEC > 4)
        {
            break;
        }

        for (int i = 1 ; i <= n ; ++i)
        {
            t[i].clear();
            std::shuffle(g[i].begin(), g[i].end(), rng);
        }

        std::fill(vis + 1, vis + 1 + n, false);
        std::fill(price + 1, price + 1 + n, 0);
        int root = rng() % n + 1;
        chain.clear();

        dfs(root, 0);
        for (int i = 1 ; i <= n ; ++i)
        {
            if (sz[i] == 1)
            {
                root = i;
                break; 
            }
        }

        dfsSZ(root, 0);
        dfsS(root, 0, 1, n);

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

        assert(cnt == n);
        while (chain.size() > 1 && par[chain[chain.size() - 2]] == chain.back())
        {
            chain.pop_back();
        }

        // std::cout << "hereeeeeeee\n";
        llong res = calcCost();
        if (calcCost() < mySol)
        {
            mySol = res;
            for (int i = 1 ; i <= n ; ++i)
            {
                ansPar[i] = par[i];
            }

            for (int i = 1 ; i <= n ; ++i)
            {
                ansSZ[i] = sz[i];
            }

            ansChain = chain;
        }
    }

    int ptr = 1;
    int last = -1;
    llong res = 0;
    std::vector <int> currChain;
    std::vector <std::vector <int>> answer;
    std::fill(vis + 1, vis + 1 + n, false);
    for (const int &u : ansChain)
    {
        if (last != -1)
        {
            res += (price[u] - price[last]) * (price[u] - price[last]);
            if (ansSZ[u] == 1)
            {
                currChain.push_back(u);
                answer.push_back(currChain);
                currChain.clear();
            }
        }

        currChain.push_back(u);
        last = u;
    }

    assert(currChain.size() == 1);
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cout << price[i] << ' ';
    }

    std::cout << '\n';
    std::cout << answer.size() << '\n';
    for (const auto &curr : answer)
    {
        std::cout << curr.size();
        for (const int &u : curr)
        {
            std::cout << ' ' << u;
        }

        std::cout << '\n';
    }
}

void input()    
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> s[i];   
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void fastIOI()
{
    // freopen("taxi.in", "r", stdin);
    // freopen("taxi.out", "w", stdout);
    
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    begTime = clock();
    fastIOI();
    input();
    solve();

    return 0;
}