#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define int long long

using namespace std;

const int MAXN=1e5+5;

mt19937 mt(rand());

int n,m;
int a[MAXN];

vector<ll> w;
ll val[MAXN];
vector<int> edges[MAXN];

ll S,minS=2e18;
vector<ll> solW;
vector<int> solPath;

vector<int> adj[MAXN];
vector<int> tr[MAXN];
vector<int> bck[MAXN];
int par[MAXN];
int depth[MAXN];

int roots[MAXN];

vector<int> path;
bool used[MAXN];
int usedCnt=0;
int ptr[MAXN];
vector<int> order;
int out[MAXN];
int pos;
int minDepth;
int curR;


void dfs1(int v)
{
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i]==par[v]) continue;
        if(!depth[adj[v][i]])
        {
            depth[adj[v][i]]=depth[v]+1;
            tr[v].push_back(adj[v][i]);
            par[adj[v][i]]=v;
            dfs1(adj[v][i]);
        }
        else if(depth[adj[v][i]]<depth[v])
        {
            bck[v].push_back(adj[v][i]);
        }
    }
}

void dfs2(int v)
{
    order.push_back(v);
    for(int i=0;i<tr[v].size();i++)
    {
        dfs2(tr[v][i]);
    }
    out[v]=order.size()-1;
}

void add(int v)
{
    path.push_back(v);
    if(!used[v]) usedCnt++;
    used[v]=1;
    if(v==order[pos]) pos++;
}

void contPath(int v)
{
    add(v);
    if(usedCnt==n)
    {
        path.push_back(-1);
        return;
    }
    if(depth[v]<minDepth)
    {
        minDepth=depth[v];
        curR=v;
    }

    for(;ptr[v]<tr[v].size();ptr[v]++)
    {
        if(pos>out[tr[v][ptr[v]]]) continue;
        contPath(tr[v][ptr[v]]);
        if(path.back()==-1) return;
    }
    if(par[v]!=path[path.size()-2])
    {
        contPath(par[v]);
        if(path.back()==-1) return;
    }
    if(pos>out[curR])
    {
        for(int i=0;i<bck[v].size();i++)
        {
            if(depth[bck[v][i]]<minDepth) contPath(bck[v][i]);
            if(path.back()==-1) return;
        }
    }

    path.push_back(-1);
    return;
}

bool cmp(int x,int y)
{
    return depth[x]>depth[y];
}

void find_path(int v)
{
    depth[v]=1;
    par[v]=-1;
    dfs1(v);
    for(int i=1;i<=n;i++) sort(bck[i].begin(), bck[i].end(), cmp);

    dfs2(v);

    int cur=v;
    add(cur);
    while(tr[cur].size()>0)
    {
        cur=tr[cur][0];
        add(cur);
    }
    path.push_back(-1);
    while(usedCnt<n)
    {
        minDepth=n+1;
        curR=0;
        contPath(path[path.size()-2]);
    }
}

pair<ll,pair<ll,ll> > swp(int u,int v)
{
    ll ret=val[u]+val[v];
    ll newu=0;
    ll newv=0;
    for(int i=0;i<edges[u].size();i++)
    {
        if(edges[u][i]==v) continue;
        newu+=(w[v]-w[edges[u][i]])*(w[v]-w[edges[u][i]]);
    }
    for(int i=0;i<edges[v].size();i++)
    {
        if(edges[v][i]==u) continue;
        newv+=(w[u]-w[edges[v][i]])*(w[u]-w[edges[v][i]]);
    }
    return {ret-newu-newv, {newu, newv}};
}

void opt()
{
    int iter=1500;
    for(int i=0;i<iter;i++)
    {
        int u=mt()%n+1;
        int v=mt()%n+1;
        if(u==v) v=v+1-(v==n ? n : 0);
        auto diff=swp(u,v);
        if(diff.fi<0)
        {
            swap(w[u], w[v]);
            val[u]=diff.se.fi;
            val[v]=diff.se.se;
            S+=diff.fi;
        }
    }
}

void init()
{
    int memsz=(n+1)*sizeof(int);
    int memszLL=(n+1)*sizeof(ll);
    memset(depth,0,memsz);
    for(int i=0;i<=n;i++) tr[i].clear();
    for(int i=0;i<=n;i++) bck[i].clear();
    memset(par,0,memsz);

    order.clear();
    memset(out,0,memsz);

    path.clear();
    memset(ptr,0,memsz);
    memset(used,0,memsz);
    usedCnt=0;
    pos=0;

    S=0;
    memset(val,0,memszLL);
    for(int i=0;i<=n;i++) edges[i].clear();
}

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

cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++)
{
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

sort(a,a+n);
w.resize(n+1);

iota(roots,roots+n,1);
shuffle(roots,roots+n,mt);
for(int rt=0;rt<min(n,(long long)150);rt++)
{
    init();

    find_path(roots[rt]);

    for(int i=0;i<order.size();i++) w[order[i]]=a[i];
    for(int i=1;i<path.size();i++)
    {
        if(path[i]==-1 || path[i-1]==-1) continue;
        ll tmp=(w[path[i]]-w[path[i-1]])*(w[path[i]]-w[path[i-1]]);
        S+=tmp;
        val[path[i]]+=tmp;
        val[path[i-1]]+=tmp;
        edges[path[i]].push_back(path[i-1]);
        edges[path[i-1]].push_back(path[i]);
    }

    //opt();

    if(S<minS)
    {
        minS=S;
        solW=w;
        solPath=path;
    }
}

cout<<solW[1];
for(int i=2;i<=n;i++) cout<<" "<<solW[i];
cout<<endl;
int days=0;
for(int i=1;i<solPath.size();i++) if(solPath[i]==-1) days++;
cout<<days<<endl;
vector<int> tmp;
for(int i=0;i<solPath.size();i++)
{
    if(solPath[i]==-1)
    {
        cout<<tmp.size();
        for(int j=0;j<tmp.size();j++) cout<<" "<<tmp[j];
        cout<<endl;
        tmp.clear();
    }
    else tmp.push_back(solPath[i]);
}

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