#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

ll N, M, S[100500], P[100500], D = 1, p = 1, RS[100500], globj, K, BS[100500], n, s, globi;
vector<int> VG[100500];
vector<int> VGcopy[100500];
vector<int> PATH;
vector<int> TS[1000500];
vector<int> FS[1000500];
float Score = 1e30;
mt19937_64 rng;
clock_t start, finish;

bool cmp(int a, int b)
{
    int cnt1 = 0;
    int cnt2 = 0;
    for(int i = 0; i < VG[a].size(); i++)
        if(P[VG[a][i]] == 0)
            cnt1++;
    for(int i = 0; i < VG[b].size(); i++)
        if(P[VG[b][i]] == 0)
            cnt2++;
    return cnt1 < cnt2;
}
bool revcmp2(int a, int b)
{
    int cnt1 = 0;
    int cnt2 = 0;
    for(int i = 0; i < VG[a].size(); i++)
        if(P[VG[a][i]] == 0)
            cnt1++;
    for(int i = 0; i < VG[b].size(); i++)
        if(P[VG[b][i]] == 0)
            cnt2++;
    return cnt1 > cnt2;
}
bool revcmp1(int a, int b)
{
    int x = VG[a].size();
    int y = VG[b].size();
    return x > y;
}
bool cmp1(int a, int b)
{
    int x = VG[a].size();
    int y = VG[b].size();
    return x < y;
}
bool revcmp(int a, int b)
{
    return a > b;
}
void IN()
{
	 freopen("taxi.in", "r", stdin);
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++)
        scanf("%d", &S[i]);
    for(int i = 1; i <= M; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        VG[a].pb(b);
        VG[b].pb(a);
    }
}
void TEMPOUT()
{
    for(int i = 1; i <= N; i++)
        printf("%d ", RS[i]);
    printf("\n%d\n", D);
    for(int i = 1; i <= D; i++)
    {
        printf("%d ", TS[i].size());
        for(int j = 0; j < TS[i].size(); j++)
            printf("%d ", TS[i][j]);
        printf("\n");
    }
}
void OUT()
{
	 freopen("taxi.out", "w", stdout);
    for(int i = 1; i <= N; i++)
        printf("%d ", BS[i]);
    printf("\n%d\n", K);
    for(int i = 1; i <= K; i++)
    {
        printf("%d ", FS[i].size());
        for(int j = 0; j < FS[i].size(); j++)
            printf("%d ", FS[i][j]);
        printf("\n");
    }
}
float CALC(ll A[], vector<int> V[])
{
    float sum = 0;
    for(int i = 1; i <= D; i++)
        for(int j = 1; j < V[i].size(); j++)
        {
            ll x = RS[V[i][j]] - RS[V[i][j - 1]];
            sum += x * x;
        }
    return sum * D;

}
void DFS(int node)
{
	if(globj == 6)
		sort(VG[node].begin(), VG[node].end(), revcmp2);
	if(globj == 5)
		sort(VG[node].begin(), VG[node].end(), cmp);
	P[node] = 1;
	PATH.pb(node);
	for(int i = 0; i < VG[node].size(); i++)
	{
		if(!P[VG[node][i]])
		{
			DFS(VG[node][i]);
			PATH.pb(node);
		}
	}
}
void RECONSTRUCT(vector<int> V[])
{
	unordered_set<int> S;
	unordered_set<int> NS;
	for(int i = 0; i < PATH.size(); i++)
	{
	    if(NS.size() == N)
            break;
	    if(S.find(PATH[i]) == S.end())
            S.insert(PATH[i]);
        else
        {
            D++;
            V[D].pb(PATH[i - 1]);
            S.clear();
            S.insert(PATH[i]);
        }
        NS.insert(PATH[i]);
		V[D].pb(PATH[i]);
	}
}
void PRESTIGE(bool b, vector<int> V[])
{
    int k = 1;
    memset(RS, 0, sizeof(RS));
    if(b)
        sort(S + 1, S + N + 1);
    else
        sort(S + 1, S + N + 1, revcmp);

    for(int i = 1; i <= D; i++)
    {
        for(int j = 0; j < V[i].size(); j++)
        {
            if(RS[V[i][j]] == 0)
            {
                RS[V[i][j]] = S[k];
                k++;
            }
        }
    }
}
void SORTING(int n)
{
    if(n == 1)
        for(int i = 1; i <= N; i++)
            sort(VG[i].begin(), VG[i].end(), cmp1);
    if(n == 2)
        for(int i = 1; i <= N; i++)
            sort(VG[i].begin(), VG[i].end());
    if(n == 3)
        for(int i = 1; i <= N; i++)
            sort(VG[i].begin(), VG[i].end(), revcmp);
    if(n == 4)
        for(int i = 1; i <= N; i++)
            sort(VG[i].begin(), VG[i].end(), revcmp1);
    if(n == 10)
        sort(VG[globi].begin(), VG[globi].end(), cmp1);
    if(n == 9)
        sort(VG[globi].begin(), VG[globi].end());
    if(n == 8)
        sort(VG[globi].begin(), VG[globi].end(), revcmp1);
    if(n == 7)
        sort(VG[globi].begin(), VG[globi].end(), revcmp);
}
void PRES(vector<int> V[])
{
    PRESTIGE(0, V);
    float x = CALC(RS, V);
    PRESTIGE(1, V);
    float y = CALC(RS, V);
    if(x < y)
        PRESTIGE(0, V);
    else
        PRESTIGE(1, V);
}
void RESET()
{
    for(int i = 1; i <= D; i++)
        TS[i].clear();
    D = 1;
    PATH.clear();
    memset(P, 0, sizeof(P));
}
bool BETTER()
{
    PRES(TS);
    if(CALC(RS, TS) < Score)
    {
        Score = CALC(RS, TS);
        return true;
    }
    return false;
}
void BRUTE(int i, int j)
{
    globj = j;
    globi = i;
    RESET();
    if(globj == 5 or globj == 6)
    {
        for(int l = 1; l <= 4; l++)
        {
            RESET();
            SORTING(l);
            DFS(i);
            RECONSTRUCT(TS);
            PRES(TS);
            if(BETTER())
            {
                for(int k = 1; k <= K; k++)
                    FS[k].clear();
                n = i;
                s = j;
                cout << CALC(RS, TS) << " Start " << i << " Sort " << j << " Dana " <<  D << " Podsort " << l << endl;
                //TEMPOUT();
                K = D;
                memcpy(BS, RS, sizeof(BS));
                for(int k = 1; k <= K; k++)
                    for(int p = 0; p < TS[k].size(); p++)
                        FS[k].pb(TS[k][p]);
            }
        }
    }
    else
    {
        SORTING(j);
        DFS(i);
        RECONSTRUCT(TS);
        PRES(TS);
        if(BETTER())
        {
            for(int k = 1; k <= K; k++)
                FS[k].clear();
            n = i;
            s = j;
            cout << CALC(RS, TS) << " Start " << i << " Sort " << j << " Dana " <<  D << endl;
            //TEMPOUT();
            K = D;
            memcpy(BS, RS, sizeof(BS));
            for(int k = 1; k <= K; k++)
                for(int l = 0; l < TS[k].size(); l++)
                    FS[k].pb(TS[k][l]);
        }
    }

}
void SOLVE()
{
    start = clock();
    K = 0;
    if(N <= 1000)
    {
        for(int i = 1; i <= N; i++)
            for(int j = 0; j < VG[i].size(); j++)
                VGcopy[i].pb(VG[i][j]);
        for(int i = 1; i <= N; i++)
        {
            globi = i;
            finish = clock();
            if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
            if(K == 1)
                break;
            for(int j = 1; j <= 10; j++)
            {
                finish = clock();
                if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
                BRUTE(i, j);
                for(int i = 1; i <= N; i++)
                    VG[i].clear();
                for(int i = 1; i <= N; i++)
                    for(int j = 0; j < VGcopy[i].size(); j++)
                        VG[i].pb(VGcopy[i][j]);
            }
        }
        for(int i = 1; i >= N; i++)
        {
            globi = i;
            finish = clock();
            if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
            if(K == 1)
                break;
            for(int j = 10; j >= 1; j--)
            {
                finish = clock();
                if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
                BRUTE(i, j);
                for(int i = 1; i <= N; i++)
                    VG[i].clear();
                for(int i = 1; i <= N; i++)
                    for(int j = 0; j < VGcopy[i].size(); j++)
                        VG[i].pb(VGcopy[i][j]);
            }

        }
    }
    else if(N <= 10000)
    {
        for(int i = N; i >= N - 50; i--)
        {
            finish = clock();
            if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
            globi = i;
            for(int j = 10; j >= 0; j--)
            {
                finish = clock();
                if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
                if(K == 1)
                    break;
                globj = j;
                RESET();
                SORTING(j);
                DFS(i);
                RECONSTRUCT(TS);
                PRES(TS);
                if(BETTER())
                {
                    for(int k = 1; k <= K; k++)
                        FS[k].clear();
                    n = i;
                    s = j;
                    cout << CALC(RS, TS) << " Start " << i << " Sort " << j << " Dana " <<  D << endl;
                    //TEMPOUT();
                    K = D;
                    memcpy(BS, RS, sizeof(BS));
                    for(int k = 1; k <= K; k++)
                        for(int l = 0; l < TS[k].size(); l++)
                            FS[k].pb(TS[k][l]);
                }
            }
            if(K == 1)
                break;
        }
    }
    else
    {
        for(int i = 1; i <= 5; i++)
        {
            finish = clock();
            if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
            globi = i;
            for(int j = 10; j >= 0; j--)
            {
                finish = clock();
                if((finish - start) / CLOCKS_PER_SEC > 3.5)
                    break;
                globj = j;
                RESET();
                SORTING(j);
                DFS(i);
                RECONSTRUCT(TS);
                PRES(TS);
                if(BETTER())
                {
                    for(int k = 1; k <= K; k++)
                        FS[k].clear();
                    n = i;
                    s = j;
                    cout << CALC(RS, TS) << " Start " << i << " Sort " << j << " Dana " <<  D << endl;
                    //TEMPOUT();
                    K = D;
                    memcpy(BS, RS, sizeof(BS));
                    for(int k = 1; k <= K; k++)
                        for(int l = 0; l < TS[k].size(); l++)
                            FS[k].pb(TS[k][l]);
                }
            }
        }
    }
    finish = clock();
    cout << "Vreme = " << finish - start << endl;
}
int main()
{
	IN();
	SOLVE();
	OUT();
	return 0;
}