#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
vector<int> t2;
vector<int> t;
vector<int> mint;
vector<int> v[maxn];
int ans=1e9;
int parent[maxn];
int used[maxn];
int br=1;
bool f2;
vector<int> otg[maxn];
vector<int> minotg[maxn];
int minbr=1e9;
void dfs(int vr, int p, int sum, int left, bool f)
{
    //cout<<vr<<"-"<<br<<endl;
    //if(f2)return;
    if(f==0)otg[br].push_back(vr);
    else otg[br+1].push_back(vr);
    if(left==0)
    {
        if(br<minbr)
        {
            ans=min(ans,sum*br);

            minbr=br;
            for(int i=1; i<=br; i++)
            {
                minotg[i]=otg[i];
            }
            mint=t;
        }
        f2=1;
        return;
    }
    used[vr]=1;
    parent[vr]=p;
    for(int i=0; i<v[vr].size(); i++)
    {
        ///cout<<v[vr][i]<<endl;
        if(!used[v[vr][i]])
        {
            if(f)br++;
            dfs(v[vr][i],vr,sum+abs(t[vr]-t[v[vr][i]])*abs(t[vr]-t[v[vr][i]]),left-1,0);
        }
    }
    if(p!=-1)
    {
        if(f==0)otg[br+1].push_back(vr);
        dfs(p,parent[p],sum+abs(t[vr]-t[p])*abs(t[vr]-t[p]),left,1);
    }
}
int main()
{

    freopen("taxi.in","r",stdin);
    freopen("taxi.out","w",stdout);

    auto start = std::chrono::system_clock::now();
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,m;
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        int k;
        cin>>k;
        t2.push_back(k);
    }
    sort(t2.begin(),t2.end());
    int k=0;
    t.resize(n+1,0);
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        if(!t[a])t[a]=t2[k++];
        if(!t[b])t[b]=t2[k++];
    }
    for(int i=1; i<=n; i++)
    {
        memset(used,0,sizeof(used));
        for(int i=0; i<n; i++)otg[i].clear();
        br=1;
        f2=0;
        dfs(i,-1,0,n-1,0);

        /* cout<<br<<endl;
         for(int i=1; i<=br; i++)
         {
             for(int j=0; j<otg[i].size(); j++)cout<<otg[i][j]<<" ";
             cout<<endl;
         }*/
    }
    while(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count()<4900)
    {
        random_shuffle(t.begin()+1,t.end());
        int k=0;
        int otg2=0;
        for(int i=1; i<=minbr; i++)
        {
            for(int j=1; j<minotg[i].size(); j++)
            {
                otg2+=abs(t[minotg[i][j]]-t[minotg[i][j-1]])*abs(t[minotg[i][j]]-t[minotg[i][j-1]]);
            }
        }
        if(otg2*minbr<ans)
        {
            mint=t;
            ans=otg2;
        }

    }
    // cout<<ans<<endl;
    for(int i=1; i<=n; i++)
    {
        if(i>1)cout<<" ";
        cout<<mint[i];
    }
    cout<<endl;
    cout<<minbr<<endl;
    for(int i=1; i<=minbr; i++)
    {
        cout<<minotg[i].size();
        for(int j=0; j<minotg[i].size(); j++)
        {
            cout<<" "<<minotg[i][j];
        }
        cout<<endl;
    }
    return 0;
}