#include<bits/stdc++.h>
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int brnext,in;
};
bool cmp(cell a1,cell a2)
{
    return a1.brnext<a2.brnext;
}
int n,m,a[100005],b[100005],c[100005],used[100005],used1[100005],usedotg[100005],brr[100005],br=1,lead[100005],usedl[100005],l=1,brused[100005],brlead[100005],brchild[100005];
unsigned long long int otg=1000000000000000001,seg;
vector<int>v[100005];
int days=1,daysotg;
vector<int>d[100005],dotg[100005],last;
void make_lead(int beg,int p)
{
    usedl[beg]=1;
    int w=0;
    last.push_back(beg);
    for(long long int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        if(!usedl[w])make_lead(w,beg);
        else if(w!=p)
        {
            if(!lead[w])
            {
                lead[w]=l;
                l++;
            }
            int j=1;
            while(lead[last[last.size()-j]]!=lead[w])
            {
                lead[last[last.size()-j]]=lead[w];
                j++;
            }
        }
    }
    last.pop_back();
}
void filllead()
{
    for(int i=1; i<=n; i++)
    {
        if(!lead[i])
        {
            lead[i]=l;
            l++;
        }
        brlead[lead[i]]++;
    }
}
void find_br(int beg)
{
    int w=0;
    brused[beg]=1;
    for(int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        if(!brused[w])
        {
            find_br(w);
            brchild[beg]+=brchild[w];
        }
    }
    brchild[beg]++;
}
vector<cell>curent[100005];
int minu[100005];
void bfs(int beg)
{
    int w=0,mseg=0;
    used1[beg]=1;
    used[beg]=a[br];
    br++;
    minu[lead[beg]]++;
    for(int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        if(!used1[w])
        {
            cell o;
            o.in=w;
            if(lead[beg]!=lead[w])
            {
                mseg+=brchild[w];
                o.brnext=brchild[w];
            }
            else o.brnext=brchild[beg];
            curent[beg].push_back(o);
        }
    }
    for(int i=0; i<curent[beg].size(); i++)
    {
        if(lead[curent[beg][i].in]==lead[beg])curent[beg][i].brnext-=(mseg+minu[beg]);
    }
    sort(curent[beg].begin(),curent[beg].end(),cmp);
    for(int i=0; i<curent[beg].size(); i++)
    {
        w=curent[beg][i].in;
        if(!used1[w])
        {
            d[days].push_back(beg);
            bfs(w);
            minu[beg]+=minu[w];
        }
    }
    d[days].push_back(beg);
    if(curent[beg].size()==0)
    {
        days++;
        d[days].push_back(beg);
    }
}
void dfs(int beg)
{
    int w,kk=0;
    used1[beg]=1;
    used[beg]=a[br];
    br++;
    for(int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        if(!used1[w])
        {
            d[days].push_back(beg);
            kk++;
            dfs(w);
        }
    }
    d[days].push_back(beg);
    if(!kk)
    {
        days++;
        d[days].push_back(beg);
    }
}
void check()
{
    unsigned long long int g=0,h=0;
    for(int i=1; i<=days; i++)
    {
        for(int j=1; j<d[i].size(); j++)
        {
            h=abs(used[d[i][j]]-used[d[i][j-1]]);
            seg+=h*h;
            if(seg>=1000000000000000001/days+1)
            {
                for(long long int i=1; i<=n; i++)brr[i]=0;
                seg=0;
                return;
            }
            if(!used[d[i][j]])
            {
                brr[d[i][j]]=1;
                g++;
            }
            if(g==n)break;
        }
    }
    seg*=days;
    if(seg<=otg)
    {
        otg=seg;
        for(int i=1; i<=days; i++)
        {
            dotg[i]=d[i];
        }
        for(int i=days+1; i<=daysotg; i++)
        {
            dotg[i].clear();
        }
        for(int i=1; i<=n; i++)
        {
            usedotg[i]=used[i];
        }
        daysotg=days;
    }
    for(int i=1; i<=n; i++)brr[i]=0;
    seg=0;
}
void read()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        used[i]=-1;
    }
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1; i<=m; i++)
    {
        cin>>b[i]>>c[i];
        v[b[i]].push_back(c[i]);
        v[c[i]].push_back(b[i]);
    }
    make_lead(1,0);
    filllead();
    if(n<=1000)
    {
        for(int i=n; i>=1; i--)
        {
            find_br(i);
            bfs(i);
            days--;
            check();
            for(int j=1; j<=n; j++)
            {
                d[j].clear();
                curent[j].clear();
                used[j]=-1;
                used1[j]=0;
                brchild[j]=0;
                brused[j]=0;
                minu[j]=0;
            }
            br=1;
            days=1;
            dfs(i);
            days--;
            check();
            for(int j=1; j<=n; j++)
            {
                d[j].clear();
                used[j]=-1;
                used1[j]=0;
            }
            br=1;
            days=1;
        }
    }
    else if(n<=10000)
    {
        if(n<=8000)
        {
            for(int i=n; i>=1; i--)
            {
                find_br(i);
                bfs(i);
                days--;
                check();
                for(int j=1; j<=n; j++)
                {
                    d[j].clear();
                    curent[j].clear();
                    used[j]=-1;
                    used1[j]=0;
                    brchild[j]=0;
                    brused[j]=0;
                    minu[j]=0;
                }
                br=1;
                days=1;
            }
        }
        else
        {
            for(int i=n; i>=n-500; i--)
            {
                find_br(i);
                bfs(i);
                days--;
                check();
                for(int j=1; j<=n; j++)
                {
                    d[j].clear();
                    curent[j].clear();
                    used[j]=-1;
                    used1[j]=0;
                    brchild[j]=0;
                    brused[j]=0;
                    minu[j]=0;
                }
                br=1;
                days=1;
            }
        }
    }
    else
    {
        for(int i=n; i>=n-200; i--)
        {
            find_br(i);
            bfs(i);
            days--;
            check();
            for(int j=1; j<=n; j++)
            {
                d[j].clear();
                curent[j].clear();
                used[j]=-1;
                used1[j]=0;
                brchild[j]=0;
                brused[j]=0;
                minu[j]=0;
            }
            br=1;
            days=1;
        }
    }
    int g=0;
    for(int i=1; i<=n; i++)
    {
        cout<<usedotg[i]<<" ";
    }
    cout<<endl<<daysotg<<endl;
    for(int i=1; i<=n; i++)
    {
        used[i]=0;
    }
    for(int i=1; i<=daysotg; i++)
    {
        cout<<dotg[i].size()<<" ";
        for(int j=0; j<dotg[i].size(); j++)
        {
            cout<<dotg[i][j]<<" ";
            if(!used[dotg[i][j]])
            {
                used[dotg[i][j]]=1;
                g++;
            }
            if(g==n)
            {
                cout<<endl;
                break;
            }
        }
        cout<<endl;
    }
}
int main()
{
#ifdef ONLINE_JUDGE
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
#endif
    speed();
    read();
    return 0;
}