#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAXM = 500000 + 5;

long long s[MAXM];
vector <int> G[MAXM];
int n, m;

vector <int> tmp;
bool used[MAXM];

int cntUsed = 0;

void dfs(int s)
{
    if (cntUsed >= n) return;
    for (auto x: G[s])
    {
        if (used[x]) continue;
        used[x] = 1;
        cntUsed++;

        tmp.push_back(x);
        dfs(x);
        tmp.push_back(s);
    }
}

vector <vector<int>> ans;

void getAns()
{
    memset(used, 0, sizeof(used));
    used[tmp[0]] = 1;
    int ind = -1;
    for (int i = 0; i < tmp.size(); i++)
    {
        if (used[tmp[i]])
        {
            memset(used, 0, sizeof(used));
            ans.push_back(vector<int>());
            ind++;
            if (ind != 0) ans[ind].push_back(ans[ind-1].back());
        }
        ans[ind].push_back(tmp[i]);
        used[tmp[i]] = 1;
    }
}

void solve()
{
    ans.clear();
    tmp.clear();
    for (int i = 0; i <= n; i++)
        used[i] = 0;
    cntUsed = 0;
    dfs(1);
    getAns();
}

long long w[MAXM];

long long eval()
{
    long long ret = 1;

    for (int i = 1; i < tmp.size(); i++)
    {
        long long add =(s[tmp[i]] - s[tmp[i-1]]) * (s[tmp[i]] - s[tmp[i-1]]);
        ret += add;
        w[tmp[i]] += add;
        if (ret < 0 || ret > 1e18) return 1e18;
    }

    ret *= ans.size();
    if (ret < 0 || ret > 1e18) return 1e18;

    return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    solve();

    srand(42);
    long long bestVal = 1e18;
    auto bestAns = ans;

    while ((double)(clock()) / CLOCKS_PER_SEC < 4.0)
    {
        int rand1 = 1 + rand() % n;
        int rand2 = 1 + rand() % n;
        if (rand1 == rand2) continue;

        swap(s[rand1], s[rand2]);

//        solve();

        long long val = eval();
        if (val > bestVal)
        {
            swap(s[rand1], s[rand2]);
        }
        else
        {
            bestVal = val;
//            bestAns = ans;
        }
    }


    for (int i = 1; i <= n; i++)
        cout << s[i] << " ";
    cout << endl;

    cout << bestAns.size() << endl;
    for (auto x: bestAns)
    {
        cout << x.size();
        for (auto y: x) cout << " " << y;
        cout << endl;
    }

    return 0;
}
/**
6 6
3 1 4 6 2 8
1 2
3 6
2 4
2 3
5 2
6 1

*/