#include<bits/stdc++.h>
using namespace std;
int n, m, x, y, taj;
vector<int> grad[200050];
bool poseceni[200050];
int odakle[200050];
int brposecenih;
int ispis[200050], br, brmaks;
int velicina[200050];
int k;
int srez[200050];
unsigned long long skor,minskor;
int s[200050];
bool provera;
int brojl;
struct slog
{
    int brojsuseda;
    int vred;
};
slog strakt[200050];

bool cmp(int a, int b)
{
    return grad[a].size() < grad[b].size();
}

bool cmp1(slog a, slog b)
{
    return a.brojsuseda<b.brojsuseda;
}
unsigned long long izrskor()
{
    unsigned long long rez=0;
    for(int i=2; i<=brmaks; i++)
      rez = rez + ((srez[ispis[i]]-srez[ispis[i-1]])*(srez[ispis[i]]-srez[ispis[i-1]]));


    if(rez<0)
    {
        provera=1;
        rez=0;
    }

    rez=rez*k;
    if(rez<0)
    {
        provera=1;
        rez=0;
    }
    return rez;
}


void ULAZ()
{
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", &s[i]);

    for(int i=1; i<=m; i++)
    {
        scanf("%d %d", &x, &y);

        strakt[x].brojsuseda++;
        strakt[y].brojsuseda++;

        grad[x].push_back(y);
        grad[y].push_back(x);
    }

    for(int i=1; i<=n; i++)
        strakt[i].vred=i;

    for(int i=1; i<=n; i++)
        sort(grad[i].begin(), grad[i].end(), cmp);
}




void DFS(int r)
{
    if(poseceni[r]==0) ///Ako nije posecen
        brposecenih++; ///broj posecenih se poveca jer ce ga posetiti
    poseceni[r]=1; ///Poseti ga

    if(brposecenih<n) ///Ako jos ima neposecenih
    {
        br++;         ///Poveca br ispisa
        //cout << r << " " << br << " uso" << endl;
        ispis[br]=r;  ///Stavi ga na to mesto u nizu ispisa
    }

    else   ///Ako su svi poseceni
    {
        if(br!=0)
        {
            br++;
            ispis[br]=r; ///Niz ispisa uzima poslednji element
            //cout << r << " " << br << endl;
        }
        if(br>0)       ///Zbog nekih bagova ovo garantuje ispravno zavrsavanje
            brmaks=br+1;
        br=0;
        return;
    }

    vector<int>::iterator i;   ///Standardni DFS
    for (i = grad[r].begin(); i != grad[r].end(); i++)
    {
        if(poseceni[*i]==0)
        {
            //cout << *i << endl;
            odakle[*i]=r;
            DFS(*i);
        }
    }
    DFS(odakle[r]); ///Ako nema komsija vrati se na onaj iz koga je dosao
}



void DFSIRAJ(int ovaj)
{
   memset(poseceni, 0, sizeof(poseceni));
   memset(velicina,0,sizeof(velicina));
   memset(ispis, 0, sizeof(ispis));
   memset(srez, 0, sizeof(srez));
   memset(odakle, 0, sizeof(odakle));
   k=0;
   brposecenih=0;
   br=0;
   brmaks=0;

   DFS(ovaj); ///NISAM SIGURAN ZASTO RADI OVO ISPOD, PROVERI

   ispis[1]=ovaj;
   brmaks--;
}


void NADJI_DANE()
{
    for(int i=1; i<=brmaks; i++)
    {
        if(poseceni[ispis[i]]==1)
        {
            memset(poseceni, 0, sizeof(poseceni));
            k++;
        }
        velicina[k]++; ///Velicina je broj gradova u 1 danu
        poseceni[ispis[i]]=1; ///Poseti ovoga
    }
}

void ODREDI_PRESTIZ()
{
      sort(s+1, s+1+n);///SORTIEA S
      int brojacs=0;
      for(int i=1; i<=brmaks; i++)
      {
         if(srez[ispis[i]]==0)
         {
            brojacs++;
            srez[ispis[i]]=s[brojacs];
         }
      }

}

void OBRNI_PRESTIZ()
{
      sort(s+1, s+n+1);
      memset(srez, 0 ,sizeof(srez));
      reverse(s+1, s+1+n);
      int brojacs=0;
      for(int i=1; i<=brmaks; i++)
      {
         if(srez[ispis[i]]==0)
         {
            brojacs++;
            srez[ispis[i]]=s[brojacs];
         }
      }

}

void ISPISI()
{
    int j=1;
    for(int i=1; i<=n; i++)
        cout << srez[i] << " ";
    cout << endl << k << endl;

    for(int i=1; i<=k; i++)
    {
        if(i==1)
            cout << velicina[i] << " ";
        else
        {
            cout << velicina[i]+1 << " ";
            cout << ispis[j-1] << " ";
        }
        for(int l=j; l < j + velicina[i]; l++)
        {
            cout << ispis[l] << " ";
        }
        j=j+velicina[i];
        cout << endl;
    }
}

int BROJ()
{
    int brojacbr;
    for(int i=1; i<=n; i++)
    {
        if(strakt[i].brojsuseda==1)
            brojacbr++;
        else
            break;
    }
    return brojacbr;
}

int main ()
{
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
    ULAZ();
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sort(strakt+1, strakt+n+1, cmp1);
    int temp1;
    temp1=min(100,n);
    brojl=min(temp1,BROJ());

    if(n<=1000)
      brojl=n;

    if(n>=1000 and n<=10000)
        brojl=250;

    if(n>10000 and n<=20000)
      brojl=25;
    if(n>20000)
    {
      DFSIRAJ(strakt[1].vred);
      NADJI_DANE();
      ODREDI_PRESTIZ();
      ISPISI();
      return 0;
    }
   bool drugi=0;

   for(int i=1; i <= brojl; i++)
   {
      DFSIRAJ(strakt[i].vred);

      NADJI_DANE();
      ODREDI_PRESTIZ();
      skor=0;
      skor=izrskor();
      if( (skor <= 0 and skor < minskor) or i==1) ///>=, a ne <=
      {
         drugi=0;
         minskor = skor;
         taj=i;
      }


      OBRNI_PRESTIZ();
      skor=0;
      skor=izrskor();
      if( (skor <=0 and skor < minskor))
      {
         drugi=1;
         minskor=skor;
         taj=i;
      }
   }

   DFSIRAJ(strakt[taj].vred);

   NADJI_DANE();
   ODREDI_PRESTIZ();
   if(drugi==1)
      OBRNI_PRESTIZ();


   ISPISI();

    return 0;
}