#include<bits/stdc++.h>
using namespace std;

struct edge{
    int a,b,w;
};
vector<edge> e;
bool fff(edge p, edge q){
    return p.w<q.w;
}

int par[100001],sz[100001],val[100001],n,m;
vector<int> v[100001];

int findPar(int k){
    if(par[k]==k) return k;
    return par[k]=findPar(par[k]);
}

void join(int p, int q){
    p=findPar(p);
    q=findPar(q);
    if(sz[p]<sz[q]){par[p]=q; sz[q]+=sz[p];}
    else {par[q]=p; sz[p]+=sz[q];}
}

void dsu(int k){
    sz[k]=0;
    for(int ch:v[k]){
        if(ch!=par[k]){
            par[ch]=k;
            dsu(ch);
            sz[k]+=sz[ch]+(val[k]-val[ch])*(val[k]-val[ch]);
        }
    }
}

bool ff(int p, int q){return sz[p]<sz[q];}

int root,brl,f,ts;
vector<int> out[100001];
void calc(int k){
    if(v[k].size()==1 && k!=root){
        out[f].push_back(k);
        f++;
        if(f<brl-1){
            out[f].push_back(k);
            ts+=(val[k]-val[par[k]])*(val[k]-val[par[k]]);
        }
        return;
    }
    for(int ch:v[k]){
        if(ch!=par[k]){
            ts+=(val[k]-val[ch])*(val[k]-val[ch]);
            out[f].push_back(k);
            calc(ch);
        }
    }
    if(f==brl-1) return;
    ts+=(val[k]-val[par[k]])*(val[k]-val[par[k]]);
    out[f].push_back(k);
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

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

int i,p,q;
cin>>n>>m;
for(i=1;i<=n;i++) cin>>val[i];
//sort(val+1,val+1+n);
for(i=0;i<m;i++){
    cin>>p>>q;
    e.push_back({p,q,(val[p]-val[q])*(val[p]-val[q])});
}
sort(e.begin(),e.end(),fff);

for(i=1;i<=n;i++) par[i]=i;
for(i=1;i<=n;i++) sz[i]=1;

i=-1;
int br=0;
while(br<n-1){
    i++;
    if(findPar(e[i].a)!=findPar(e[i].b)){
        br++;
        v[e[i].a].push_back(e[i].b);
        v[e[i].b].push_back(e[i].a);
        join(e[i].a,e[i].b);
    }
}

for(i=1;i<=n;i++) if(v[i].size()==1) brl++;

int mr,ms=INT_MAX;
for(i=1;i<=n;i++) if(v[i].size()==1){
    ts=0;
    f=0;
    root=i;
    par[root]=0;
    dsu(root);
    for(int j=1;j<=n;j++) sort(v[j].begin(),v[j].end(),ff);
    calc(root);
    if(ts<ms){
        ms=ts;
        mr=root;
    }
}

f=0;
for(i=0;i<brl;i++) out[i].clear();
root=mr;
par[root]=0;
dsu(root);
for(i=1;i<=n;i++) sort(v[i].begin(),v[i].end(),ff);
calc(root);

for(i=1;i<=n;i++) cout<<val[i]<<" ";
cout<<'\n'<<brl-1<<'\n';
for(i=0;i<brl-1;i++){
    cout<<out[i].size()<<" ";
    for(int j:out[i]) cout<<j<<" ";
    cout<<'\n';
}


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