///3.16 * 1e11
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
///input
char BUFFER[6100000];
char *pos;
inline int getnum()
{
   char C;
   while ((C = *pos++) < '0');
   int num = C -= '0';
   while ((C = *pos++) >= '0') num = 10 * num + C - '0';
   return num;
}
int N, M, x, y; //input
ll PRESTIGE[100096]; //input
vector <int> VG[100096]; //graph
///dfs traversing:
int globalD; //global for DFS
int A[100096]; //current global of each node
int PATH[300096]; //current memorised path
int point; //current index in current path
int BESTPATH[300096]; //best path found
int BESTPATHLENGTH; //length of best path found
int K; //number of days
int DAYS; //current number of days
/*unordered_*/map <ll, int> POPULAR;
int NODE;
///prestiges:
ll D[100096]; //best prestiges
ll D1[100096]; //prestiges down
ll D2[100096]; //prestiges up
int pointD; //current index in prestiges
ll SUMK[100096];
ll SUMO[100096];
ll SUMO2[100096];
/*unordered_*/map <ll, int> MAP;
///scores:
ll SCORE = 1e18;
ll CSCORE;
///output:
vector <int> OUT[100096]; //path output
inline ll toMap(int aNODE, int bNODE)
{
    if(aNODE > bNODE)
    {
        swap(aNODE, bNODE);
    }
    return (aNODE * 1e11 + bNODE);
}
bool compSIZE(int A, int B)
{
    return (VG[A].size() < VG[B].size());
}
bool compPOPULAR(int A, int B)
{
    return (POPULAR[toMap(NODE, A)] > POPULAR[toMap(NODE, B)]);
}
void INPUT()
{
    freopen("taxi.in", "r", stdin);
    fread(BUFFER, 1, 6100000, stdin);
    pos = BUFFER;
    N = getnum();
    M = getnum();
    for(int i = 1; i <= N; i++)
    {
        PRESTIGE[i] = getnum();
    }
    for(int i = 1; i <= M; i++)
    {
        x = getnum();
        y = getnum();
        VG[x].push_back(y);
        VG[y].push_back(x);
    }
}
int LIMIT1()
{
    if(N <= 1000)
    {
       return N;
    }
    if(N <= 10000)
    {
        return  600;
    }
    return 100;
}
int LIMIT2()
{
    if(N <= 100)
    {
        return 4950;
    }
    if(N <= 1000)
    {
        return 200;
    }
    return 0;
}
void SUMOS()
{
    MAP.clear();
    memset(SUMK, 0, sizeof(SUMK));
    memset(SUMO, 0, sizeof(SUMO));
    memset(SUMO2, 0, sizeof(SUMO2));
    for(int i = 2; i <= BESTPATHLENGTH; i++)
    {
        MAP[toMap(BESTPATH[i], BESTPATH[i - 1])]++;
        SUMK[BESTPATH[i]]++;
        SUMO[BESTPATH[i]] += D[BESTPATH[i - 1]];
        SUMO2[BESTPATH[i]] += D[BESTPATH[i - 1]] * D[BESTPATH[i - 1]];
        SUMK[BESTPATH[i - 1]]++;
        SUMO[BESTPATH[i - 1]] += D[BESTPATH[i]];
        SUMO2[BESTPATH[i - 1]] += D[BESTPATH[i]] * D[BESTPATH[i]];
    }
    for(int i = 1; i <= N; i++)
    {
        SUMO[i] *= -2ll;
    }
}
inline ll CALC1(int index)
{
    return (D[index] * SUMO[index] + SUMO2[index] + SUMK[index] * (D[index] * D[index]));
}
inline ll CALC2(int indexA, int indexB)
{
    /*unordered_*/map <ll, int>::iterator it = MAP.find(toMap(indexA, indexB));
    if(it == MAP.end())
    {
        return (D[indexA] * SUMO[indexB] + SUMO2[indexB] + SUMK[indexB] * (D[indexA] * D[indexA]) + D[indexB] * SUMO[indexA] + SUMO2[indexA] + SUMK[indexA] * (D[indexB] * D[indexB]));
    }
    return (D[indexA] * SUMO[indexB] + SUMO2[indexB] + SUMK[indexB] * (D[indexA] * D[indexA]) + D[indexB] * SUMO[indexA] + SUMO2[indexA] + SUMK[indexA] * (D[indexB] * D[indexB]) + it->second * (D[indexA] - D[indexB]) * (D[indexA] - D[indexB]));
}
inline ll CALC3(ll worst, int indexW, int index)
{
    /*unordered_*/map <ll, int>::iterator it = MAP.find(toMap(indexW, index));
    if(it == MAP.end())
    {
        return (worst + CALC1(index));
    }
    return (worst + CALC1(index) - it->second * (D[indexW] - D[index]) * (D[indexW] - D[index]));
}
inline void SWAPPER(int BAD, int GOOD)
{
    if(BAD == GOOD)
    {
        return;
    }
    for(int i = 0; i < VG[BAD].size(); i++)
    {
        /*unordered_*/map <ll, int>::iterator it = MAP.find(toMap(BAD, VG[BAD][i]));
        if(it == MAP.end())
        {
            continue;
        }
        SUMO[VG[BAD][i]] +=  it->second * 2 * (D[BAD] - D[GOOD]);
        SUMO2[VG[BAD][i]] += it->second * (D[GOOD] * D[GOOD] - D[BAD] * D[BAD]);
    }
    for(int i = 0; i < VG[GOOD].size(); i++)
    {
        /*unordered_*/map <ll, int>::iterator it = MAP.find(toMap(GOOD, VG[GOOD][i]));
        if(it == MAP.end())
        {
            continue;
        }
        SUMO[VG[GOOD][i]] +=  it->second * 2 * (D[GOOD] - D[BAD]);
        SUMO2[VG[GOOD][i]] += it->second * (D[BAD] * D[BAD] - D[GOOD] * D[GOOD]);
    }
    swap(D[GOOD], D[BAD]);
}
inline bool IMPROVE()
{
    int indexBAD, indexGOOD;
    ll improvement = 0;
    for(int i = 1; i <= N; i++)
    {
        ll BAD = CALC1(i);
        for(int j = i; j <= N; j++)
        {
            if(CALC3(BAD, i, j) - CALC2(i, j) >= improvement)
            {
                improvement = CALC3(BAD, i, j) - CALC2(i, j);
                indexBAD = i;
                indexGOOD = j;
            }
        }
    }
    if(!improvement)
    {
        return false;
    }
    SWAPPER(indexBAD, indexGOOD);
    SCORE -= (K * improvement);
    return true;
}
void SWAPPING()
{
    if(N > 1000 || K == 1)
    {
        return;
    }
    SUMOS();
    int LIMIT = LIMIT2();
    while(LIMIT-- && IMPROVE());
}
void ONES()
{
    for(int i = 1; i <= N; i++)
    {
        int ones = 0;
        for(int j = 0; j < VG[i].size(); j++)
        {
            if(VG[VG[i][j]].size() == 1)
            {
                swap(VG[i][j], VG[i][ones]);
                ones++;
            }
        }
    }
}
void POPULARDFS(int node)
{
    A[node] = globalD;
    D2[node] = PRESTIGE[N - pointD];
    D1[node] = PRESTIGE[++pointD];
    PATH[++point] = node;
    NODE = node;
    sort(VG[node].begin(), VG[node].end(), compPOPULAR);
    for(int i = 0; i < VG[node].size(); i++)
    {
        if(A[VG[node][i]] != globalD)
        {
            POPULARDFS(VG[node][i]);
            PATH[++point] = node;
            POPULAR[toMap(node, VG[node][i])]++;
        }
    }
}
void DFS(int node)
{
    A[node] = globalD;
    D2[node] = PRESTIGE[N - pointD];
    D1[node] = PRESTIGE[++pointD];
    PATH[++point] = node;
    for(int i = 0; i < VG[node].size(); i++)
    {
        if(A[VG[node][i]] != globalD)
        {
            DFS(VG[node][i]);
            PATH[++point] = node;
        }
    }
}
inline ll SCORING()
{
    ll SCORE1 = 0ll, SCORE2 = 0ll;
    DAYS = 1;
    bool ADDDAY;
    /*unordered_*/set <int> SET;
    int i = 1;
    SET.insert(PATH[i]);
    while(SET.size() < N)
    {
        i++;
        if(SET.find(PATH[i]) == SET.end())
        {
            SET.insert(PATH[i]);
            ADDDAY = true;
        }
        else if(ADDDAY)
        {
            DAYS++;
            ADDDAY = false;
        }
        SCORE1 += ((D1[PATH[i]] - D1[PATH[i - 1]]) * (D1[PATH[i]] - D1[PATH[i - 1]]));
        SCORE2 += ((D2[PATH[i]] - D2[PATH[i - 1]]) * (D2[PATH[i]] - D2[PATH[i - 1]]));
    }
    point = i;
//    printf("STARTING FROM: %d\tDAYS: %d\tSCORE: %lld\n", PATH[1], DAYS, min(SCORE1, SCORE2) * DAYS);
    if(SCORE1 < SCORE2)
    {
        return SCORE1 * DAYS;
    }
    swap(D2, D1);
    return SCORE2 * DAYS;
}
inline void FINDSCOREDFS()
{
    int LIMIT = LIMIT1();
    for(int i = 1; i <= N && LIMIT; i++)
    {
        LIMIT--;
        globalD++;
        point = 0;
        pointD = 0;
        DFS(i);
        CSCORE = SCORING();
        if(CSCORE < SCORE)
        {
            SCORE = CSCORE;
            BESTPATHLENGTH = point;
            swap(PATH, BESTPATH);
            swap(D1, D);
        }
    }
}
inline void FINDSCORESIZE()
{
    for(int i = 1; i <= N; i++)
    {
        sort(VG[i].begin(), VG[i].end(), compSIZE);
    }
    int LIMIT = LIMIT1();
    for(int i = 1; i <= N && LIMIT; i++)
    {
        LIMIT--;
        globalD++;
        point = 0;
        pointD = 0;
        DFS(i);
        CSCORE = SCORING();
        if(CSCORE < SCORE)
        {
            SCORE = CSCORE;
            BESTPATHLENGTH = point;
            swap(PATH, BESTPATH);
            swap(D1, D);
        }
    }
}
inline void FINDSCOREPOPULAR()
{
    int LIMIT = LIMIT1();
    for(int i = 1; i <= N && LIMIT; i++)
    {
        LIMIT--;
        globalD++;
        point = 0;
        pointD = 0;
        POPULARDFS(i);
        CSCORE = SCORING();
        if(CSCORE < SCORE)
        {
            SCORE = CSCORE;
            BESTPATHLENGTH = point;
            swap(PATH, BESTPATH);
            swap(D1, D);
        }
    }
}
inline void FINDSCOREDFSSMALL()
{
    int LIMIT = LIMIT1();
    for(int i = 1; i <= N && LIMIT; i++)
    {
        LIMIT--;
        globalD++;
        point = 0;
        pointD = 0;
        DFS(i);
        CSCORE = SCORING();
        swap(CSCORE, SCORE);
        swap(D1, D);
        swap(PATH, BESTPATH);
        swap(point, BESTPATHLENGTH);
        swap(DAYS, K);
        SWAPPING();
        swap(CSCORE, SCORE);
        swap(D1, D);
        swap(PATH, BESTPATH);
        swap(point, BESTPATHLENGTH);
        swap(DAYS, K);
        CSCORE = SCORING();
        if(CSCORE < SCORE)
        {
            SCORE = CSCORE;
            BESTPATHLENGTH = point;
            swap(PATH, BESTPATH);
            swap(D1, D);
        }
    }
}
inline void FINDSCORESIZESMALL()
{
    for(int i = 1; i <= N; i++)
    {
        sort(VG[i].begin(), VG[i].end(), compSIZE);
    }
    int LIMIT = LIMIT1();
    for(int i = 1; i <= N && LIMIT; i++)
    {
        LIMIT--;
        globalD++;
        point = 0;
        pointD = 0;
        DFS(i);
        CSCORE = SCORING();
        swap(CSCORE, SCORE);
        swap(D1, D);
        swap(PATH, BESTPATH);
        swap(point, BESTPATHLENGTH);
        swap(DAYS, K);
        SWAPPING();
        swap(CSCORE, SCORE);
        swap(D1, D);
        swap(PATH, BESTPATH);
        swap(point, BESTPATHLENGTH);
        swap(DAYS, K);
        CSCORE = SCORING();
        if(CSCORE < SCORE)
        {
            SCORE = CSCORE;
            BESTPATHLENGTH = point;
            swap(PATH, BESTPATH);
            swap(D1, D);
        }
    }
}
inline void FINDSCOREPOPULARSMALL()
{
    int LIMIT = LIMIT1();
    for(int i = 1; i <= N && LIMIT; i++)
    {
        LIMIT--;
        globalD++;
        point = 0;
        pointD = 0;
        POPULARDFS(i);
        CSCORE = SCORING();
        swap(CSCORE, SCORE);
        swap(D1, D);
        swap(PATH, BESTPATH);
        swap(point, BESTPATHLENGTH);
        swap(DAYS, K);
        SWAPPING();
        swap(CSCORE, SCORE);
        swap(D1, D);
        swap(PATH, BESTPATH);
        swap(point, BESTPATHLENGTH);
        swap(DAYS, K);
        CSCORE = SCORING();
        if(CSCORE < SCORE)
        {
            SCORE = CSCORE;
            BESTPATHLENGTH = point;
            swap(PATH, BESTPATH);
            swap(D1, D);
        }
    }
}
void MAKEOUTPUT()
{
    K = 1;
    /*unordered_*/set <int> SET;
    int i = 0;
    for(int i = 1; i <= BESTPATHLENGTH; i++)
    {
        if(SET.find(BESTPATH[i]) == SET.end())
        {
            SET.insert(BESTPATH[i]);
        }
        else
        {
            SET.clear();
            SET.insert(BESTPATH[i]);
            OUT[++K].push_back(BESTPATH[i - 1]);
        }
        OUT[K].push_back(BESTPATH[i]);
    }
}
void TESTOUT()
{
    freopen("checker.in", "w", stdout);
    printf("%d\n", N);
    for(int i = 1; i <= N; i++)
    {
        printf("%lld ", D[i]);
    }
    printf("\n%d\n", K);
    for(int i = 1; i <= K; i++)
    {
        printf("%d ", OUT[i].size());
        for(int j = 0; j < OUT[i].size(); j++)
        {
            printf("%d ", OUT[i][j]);
        }
        printf("\n");
    }
}
void OUTPUT()
{
    freopen("taxi.out", "w", stdout);
    for(int i = 1; i <= N; i++)
    {
        printf("%lld ", D[i]);
    }
    printf("\n%d\n", K);
    for(int i = 1; i <= K; i++)
    {
        printf("%d ", OUT[i].size());
        for(int j = 0; j < OUT[i].size(); j++)
        {
            printf("%d ", OUT[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    INPUT();
    sort(PRESTIGE + 1, PRESTIGE + N + 1);
    if(N <= 100)
    {
        FINDSCOREDFSSMALL();
        FINDSCORESIZESMALL();
        FINDSCOREPOPULARSMALL();
        SWAPPING();
    }
    else if(N <= 500)
    {
        FINDSCOREDFS();
        ONES();
        FINDSCOREDFS();
        FINDSCORESIZE();
        SWAPPING();
    }
    else if(N <= 1000)
    {
        FINDSCOREPOPULAR();
        SWAPPING();
    }
    else if(N <= 10000)
    {
        ONES();
        FINDSCOREDFS();
        FINDSCOREPOPULAR();
    }
    else
    {
//        ONES();
//        FINDSCOREDFS();
        FINDSCOREPOPULAR();
    }
    MAKEOUTPUT();
    printf("DAYS: %d\tSCORE: %e\n", K, SCORE);
    OUTPUT();
//    TESTOUT();

    return 0;
}