#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;
const long long INF=1e18;

mt19937 rng(42);

int n,m;

int s[nmax],id_s=0;

int outp[nmax];

bool been[nmax];

vector<int> adj[nmax],path;

int deg[nmax];

long long best_score=INF;
int best_outp[nmax];

vector< vector<int> > best_paths;

void print_paths()
{
    for(int i=1;i<=n;i++)printf("%i ",best_outp[i]);
    printf("\n");

    printf("%i\n",best_paths.size());

    for(auto p:best_paths)
    {
        printf("%i",p.size());

        for(auto cur:p)
            printf(" %i",cur);

        printf("\n");
    }

    cerr<<best_score<<endl;
}

vector<int> adj_for_bfs[nmax];
int deg_bfs[nmax];

pair<int,int> highest_distance;

void dfs_bfs(int node,int par,int d)
{
    if(highest_distance.second<d)highest_distance={node,d};

    for(auto w:adj_for_bfs[node])
        if(w!=par)
            dfs_bfs(w,node,d+1);
}

int furthest(int node)
{
    highest_distance={-1,-1};

    dfs_bfs(node,0,0);

    return highest_distance.first;
}

bool cmp_bfs(int u,int v)
{
    return deg_bfs[u]<deg_bfs[v];
}

bool been_bfs[nmax];

void recolour(int root)
{
    for(int i=1;i<=n;i++)
    {
        been_bfs[i]=0;
        deg_bfs[i]=adj_for_bfs[i].size();
    }

    queue<int> in = queue<int> ();

    int id=0;

    in.push(root);

    while(in.size())
    {
        int tp=in.front();

        in.pop();

        if(been_bfs[tp])continue;

        for(auto w:adj_for_bfs[tp])
            deg_bfs[w]--;

        been_bfs[tp]=1;

        id++;

        outp[tp]=s[id];

        sort(adj_for_bfs[tp].begin(),adj_for_bfs[tp].end(),cmp_bfs);

        for(auto w:adj_for_bfs[tp])
            if(been_bfs[w]==0)
                in.push(w);
    }
}

bool in_unique[nmax];

int PARENT[nmax];
int ROOT(int node)
{
    if(PARENT[node]==node)return node;
    PARENT[node]=ROOT(PARENT[node]);
    return PARENT[node];
}

int order_mini[nmax];

long long actual_min()
{
    sort(outp+1,outp+n+1);

    long long MINI=1e18;

    do
    {
        long long score=0;

        for(int i=1;i<path.size();i++)
            score+=1LL*(outp[path[i]]-outp[path[i-1]])*(outp[path[i]]-outp[path[i-1]]);

        if(MINI>score)
        {
            MINI=score;

            for(int i=1;i<=n;i++)
                order_mini[i]=outp[i];
        }
    }
    while(next_permutation(outp+1,outp+n+1));

    //for(int i=1;i<=n;i++)cerr<<order_mini[i]<<" ";cerr<<endl;

    return MINI;
}

vector<int> longest_path,current_path;

void dfs_path(int node,int parent,int target)
{
    current_path.push_back(node);

    if(node==target)
    {
        longest_path=current_path;
        return;
    }

    for(auto w:adj_for_bfs[node])
        if(w!=parent)
            dfs_path(w,node,target);

    current_path.pop_back();
}

int dfs_cnt(int node,int parent,int left_block,int right_block)
{
    if(node==left_block||node==right_block)return 0;

    int cnt=1;

    for(auto w:adj_for_bfs[node])
        if(w!=parent)
            cnt+=dfs_cnt(w,node,left_block,right_block);

    return cnt;
}

int ID_LONGEST;

void bfs_part(int node,set<int> blocked,int add)
{
    queue<int> in = queue<int> ();

    in.push(node);

    while(in.size())
    {
        int tp=in.front();

        in.pop();

        if(outp[tp]!=-1||blocked.count(tp))continue;

        for(auto w:adj_for_bfs[tp])
            deg_bfs[w]--;

        ID_LONGEST+=add;

        outp[tp]=s[ID_LONGEST];

        sort(adj_for_bfs[tp].begin(),adj_for_bfs[tp].end(),cmp_bfs);

        for(auto w:adj_for_bfs[tp])
            if(outp[w]==-1)
                in.push(w);
    }
}

vector< vector<int> > get_paths()
{
    for(int i=1;i<=n;i++)
        PARENT[i]=i;

    for(int i=1;i<=n;i++)
        adj_for_bfs[i]={};

    vector< vector<int> > paths={};

    int id_path=0;

    while(id_path<path.size())
    {
        vector<int> current_path={};

        while(id_path<path.size()&&in_unique[path[id_path]]==0)
        {
            current_path.push_back(path[id_path]);

            in_unique[path[id_path]]=1;
            id_path++;
        }

        if(id_path<path.size())id_path--;

        paths.push_back(current_path);

        for(int j=1;j<current_path.size();j++)
        {
            int u=current_path[j-1],v=current_path[j];

            if(ROOT(u)!=ROOT(v))
            {
                PARENT[ROOT(u)]=ROOT(v);

                adj_for_bfs[u].push_back(v);
                adj_for_bfs[v].push_back(u);
            }

            in_unique[u]=0;
            in_unique[v]=0;

        }
    }

    return paths;
}

void dfs_paths(int node,int par)
{
    path.push_back(node);

    for(auto w:adj_for_bfs[node])
        if(w!=par)
        {
            dfs_paths(w,node);
            path.push_back(node);
        }
}

void test_paths()
{
    vector< vector<int> > paths=get_paths();

    long long cost=0;
    for(int i=1;i<path.size();i++)
    {
        cost+=1LL*(outp[path[i]]-outp[path[i-1]])*(outp[path[i]]-outp[path[i-1]]);
    }

    //for(int i=1;i<=n;i++)cerr<<outp[i]<<" ";cerr<<endl;
    //cerr<<cost*paths.size()<<" start "<<cost<<" "<<paths.size()<<endl;

    if(cost<=INF/paths.size()&&cost*paths.size()<best_score)
    {
        best_score=cost*paths.size();

        for(int i=1;i<=n;i++)best_outp[i]=outp[i];

        best_paths=paths;
    }

    int u=furthest(paths[0][0]);

    int v=furthest(u);

    recolour(v);

    cost=0;
    for(int i=1;i<path.size();i++)
        cost+=1LL*(outp[path[i]]-outp[path[i-1]])*(outp[path[i]]-outp[path[i-1]]);

    //for(int i=1;i<=n;i++)cerr<<outp[i]<<" ";cerr<<endl;
    //cerr<<cost*paths.size()<<" recolour "<<cost<<" "<<paths.size()<<endl;

    if(cost<=INF/paths.size()&&cost*paths.size()<best_score)
    {
        best_score=cost*paths.size();

        for(int i=1;i<=n;i++)best_outp[i]=outp[i];

        best_paths=paths;
    }

    longest_path={};
    current_path={};

    dfs_path(u,u,v);

    for(int i=1;i<=n;i++)
    {
        deg_bfs[i]=adj_for_bfs[i].size();
    }

    for(int i=1;i<=n;i++)
        outp[i]=-1;

    ID_LONGEST=0;

    for(int i=0;i<longest_path.size();i++)
    {
        int left_block=-1;
        if(i-1>=0)left_block=longest_path[i-1];

        int right_block=-1;
        if(i+1<longest_path.size())right_block=longest_path[i+1];

        vector< pair<int,int> > by_size={};

        for(auto w:adj_for_bfs[longest_path[i]])
            if(w!=left_block&&w!=right_block)
                by_size.push_back({dfs_cnt(w,longest_path[i],longest_path[i],longest_path[i]),w});

        sort(by_size.begin(),by_size.end());
        reverse(by_size.begin(),by_size.end());

        int total=1;
        for(auto w:by_size)
            total+=w.first;

        total=total/2;

        int total_lower=0;

        set<int> lower={left_block,right_block},upper={left_block,right_block};

        for(auto w:by_size)
            if(w.first<=total)
            {
                lower.insert(w.second);
                total=total-w.first;

                total_lower+=w.first;
            }
            else upper.insert(w.second);

        int old_ID=ID_LONGEST;

        ID_LONGEST=ID_LONGEST+total_lower+2;

        bfs_part(longest_path[i],upper,-1);

        ID_LONGEST+=total_lower-1;

        outp[longest_path[i]]=-1;

        bfs_part(longest_path[i],lower,1);
    }

    cost=0;
    for(int i=1;i<path.size();i++)
        cost+=1LL*(outp[path[i]]-outp[path[i-1]])*(outp[path[i]]-outp[path[i-1]]);

    //cerr<<cost*paths.size()<<" on shortest "<<cost<<" "<<paths.size()<<endl;
    //cerr<<cost<<" "<<paths.size()<<endl;

    if(cost<=INF/paths.size()&&cost*paths.size()<best_score)
    {
        best_score=cost*paths.size();

        for(int i=1;i<=n;i++)best_outp[i]=outp[i];

        best_paths=paths;
    }

    path={};

    for(int i=0;i<longest_path.size();i++)
    {
        path.push_back(longest_path[i]);

        int left_block=-1;
        if(i-1>=0)left_block=longest_path[i-1];

        int right_block=-1;
        if(i+1<longest_path.size())right_block=longest_path[i+1];

        for(auto w:adj_for_bfs[longest_path[i]])
            if(w!=left_block&&w!=right_block)
            {
                dfs_paths(w,longest_path[i]);

                path.push_back(longest_path[i]);
            }
    }

    paths=get_paths();

    cost=0;
    for(int i=1;i<path.size();i++)
        cost+=1LL*(outp[path[i]]-outp[path[i-1]])*(outp[path[i]]-outp[path[i-1]]);

    //cerr<<cost*paths.size()<<" on rebuild "<<cost<<" "<<paths.size()<<endl;
    //for(auto w:path)cerr<<w<<" ";cerr<<endl;

    if(cost<=INF/paths.size()&&cost*paths.size()<best_score)
    {
        best_score=cost*paths.size();

        for(int i=1;i<=n;i++)best_outp[i]=outp[i];

        best_paths=paths;
    }

    if(n<=9)
    {
        cost=actual_min();

        for(int i=1;i<=n;i++)outp[i]=order_mini[i];

        //cerr<<cost*paths.size()<<" brute "<<cost<<" "<<paths.size()<<endl;
        //cerr<<"---"<<endl;

        if(cost<=INF/paths.size()&&cost*paths.size()<best_score)
        {
            best_score=cost*paths.size();

            for(int i=1;i<=n;i++)best_outp[i]=outp[i];

            best_paths=paths;
        }
    }
}

bool cmp(int u,int v)
{
    return deg[u]<deg[v];
}

void dfs(int node)
{
    if(been[node]||id_s==n)return;

    been[node]=1;

    id_s++;

    outp[node]=s[id_s];

    path.push_back(node);

    for(auto w:adj[node])
        deg[w]--;

    if(id_s==n)
    {
        test_paths();
        return;
    }

    sort(adj[node].begin(),adj[node].end(),cmp);
    //shuffle(adj[node].begin(),adj[node].end(),rng);

    for(auto w:adj[node])
        if(been[w]==0)
        {
            dfs(w);
            path.push_back(node);
        }
}

void test(int node)
{
    path={};

    id_s=0;

    for(int i=1;i<=n;i++)been[i]=0;

    for(int i=1;i<=n;i++)
        deg[i]=adj[i].size();

    dfs(node);
}

bool cmp_ordered(int u,int v)
{
    return make_pair(adj[u].size(),u) < make_pair(adj[v].size(),v);
}

int main()
{
    freopen("taxi.in","r",stdin);
    freopen("taxi.out","w",stdout);

    double T=clock();

    scanf("%i%i",&n,&m);

    for(int i=1;i<=n;i++)scanf("%i",&s[i]);
    sort(s+1,s+n+1);

    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%i%i",&u,&v);

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> ordered={};
    for(int i=1;i<=n;i++)
        ordered.push_back(i);

    sort(ordered.begin(),ordered.end(),cmp_ordered);

    for(auto i:ordered)
    {
        if(1.0*(clock()-T)/CLOCKS_PER_SEC>4.5)break;

        test(i);
    }

    print_paths();

    return 0;
}