#include<bits/stdc++.h>
#define MAXN 100001
#pragma GCC optimize ("O3")
using namespace std;
struct node{
    int x=0;
    bool mst=false;
};
struct durvnode{
    int x=0,stx=0,sty=0;
};
struct hamnode{
    bool imali=false;
    int prev=-1,prevmask=-1;
};
time_t start,endd;
vector<node> rebra[MAXN];
bool artt[MAXN];
vector<durvnode> durvreb[MAXN];
long long st[MAXN],st1[MAXN];
bool done=false;
int n,m,dayind[MAXN],realst[MAXN],realstind=1,startnode=1;
vector<int> day,vrebra[MAXN];
int in[MAXN],nv[MAXN],vr=0,mstind=0;
bool g[MAXN],finall=false,gg[MAXN];
pair<int,int> mostove[MAXN];
void dfsmst(int x,int p,int ind){
    in[x]=vr;
    g[x]=true;
    nv[x]=vr;
    bool flag=false;
    int deca=0;
    vr++;
    int pi;
    for(int i=0;i<rebra[x].size();i++){
        if(rebra[x][i].x==p){
            pi=i;
            continue;
        }
        if(g[rebra[x][i].x]) nv[x]=min(nv[x],in[rebra[x][i].x]);
        else{
            deca++;
            dfsmst(rebra[x][i].x,x,i);
            if(nv[rebra[x][i].x]>=in[x]){
                flag=true;
            }
            nv[x]=min(nv[x],nv[rebra[x][i].x]);
        }
    }
    if(((x==1) && (deca>1)) || ((x!=1) && (flag==true))){
        artt[x]=true;
    }
    if(nv[x]>=in[x] && p!=-1){
       // cout<<p<<" "<<x<<" "<<ind<<" "<<pi<<" most\n";
        rebra[p][ind].mst=true;
        rebra[x][pi].mst=true;
        mostove[mstind].first=p;
        mostove[mstind].second=x;
        mstind++;
    }
}
int prin[MAXN];
void dfs(int x,int ind,int srt){
    prin[x]=ind;
    g[x]=true;
    //cout<<x<<" e "<<ind<<"\n";
    if(artt[x]){
        if(srt==x) g[x]=false;
        return;
    }
    for(int i=0;i<rebra[x].size();i++){
       // if(rebra[x][i].x==2) cout<<"tuka e "<<rebra[x][i].mst<<"\n";
        if(g[rebra[x][i].x] || rebra[x][i].mst) continue;
        dfs(rebra[x][i].x,ind,srt);
    }
}
int par[MAXN],obh[MAXN],daysz=0;
bool used[MAXN];
vector<pair<int,int>> izh[MAXN];
bool globalg[MAXN];
void addtopath(int x){
    day.push_back(x);
    daysz++;
    if(daysz!=1){
        vrebra[x].push_back(day[daysz-2]);
        vrebra[day[daysz-2]].push_back(x);
    }
    //   cout<<obh[i]<<" ";
    used[x]=true;
    if(!gg[x]) gg[x]=true;
    else{
        for(int i=0;i<=n;i++){
            gg[x]=false;
        }
    }
    if(realst[x]==0){
        realst[x]=realstind;
        if(realstind==n){
            done=true;;
        }
        realstind++;
    }
}
bool durvg[MAXN];
int findpath(int x,int forb){
    for(int i=0;i<=n;i++){
        par[i]=0;
        g[i]=false;
    }
    queue<int> bfs;
    int y=0,sz;
    bfs.push(x);
    g[x]=true;
    bool sv=false;
    sz=izh[x].size();
    while(sz!=0 && (izh[x][sz-1].first==forb || durvg[izh[x][sz-1].first])){
   // if(x==12) cout<<x<<" yo "<<izh[x][sz-1].first<<" "<<prin[9]<<"\n";
        izh[x].pop_back();
        sz--;
    }
    if(sz!=0){
   // if(forb==3) cout<<forb<<" zz "<<izh[x][sz-1].first<<"\n";
        sv=true;
        y=x;
    }
    while(!bfs.empty() && !sv){
        int fron=bfs.front();
        bfs.pop();
        for(int i=0;i<rebra[fron].size();i++){
            if(prin[rebra[fron][i].x] != prin[fron]) continue;
            if(!g[rebra[fron][i].x]){
                bfs.push(rebra[fron][i].x);
                g[rebra[fron][i].x]=true;
                par[rebra[fron][i].x]=fron;
                sz=izh[rebra[fron][i].x].size();
                while(sz!=0 && (izh[rebra[fron][i].x][sz-1].first==forb || durvg[izh[rebra[fron][i].x][sz-1].first])){
                    izh[rebra[fron][i].x].pop_back();
                    sz--;
                }
                if(sz!=0){
                    sv=true;
                    y=rebra[fron][i].x;
                    break;
                }
            }
        }
    }
    int curr=y,ind=0;
    //if(forb==3) cout<<y<<" "<<x<<" yo\n";
    if(y==0) return -1;
    while(curr!=x){
        //cout<<"vlizam "<<startnode<<" "<<curr<<" "<<x<<"\n";
        obh[ind]=curr;
        ind++;
        curr=par[curr];
    }
    for(int i=ind-1;i>=0;i--){
        addtopath(obh[i]);
        if(done) break;

    }
    int retval=izh[y][izh[y].size()-1].second;
    izh[y].pop_back();
    return retval;
}
int dist[MAXN];
int deqbfs(int curr,bool nextd){
    for(int i=0;i<=n;i++){
        par[i]=0;
        dist[i]=0;
        g[i]=false;
    }
    queue<int> bfs,bfs1;
    bfs.push(curr);
    g[curr]=true;
    dist[curr]=0;
    bool sv=false;
    int mxdist=0,mxi=curr;
    while(!bfs.empty() || !bfs1.empty()){
        int fron;
        if(bfs1.empty()){
            fron=bfs.front();
            bfs.pop();
        }else{
            fron=bfs1.front();
            bfs1.pop();
        }
      //  cout<<"vlizam "<<fron<<" "<<g[16]<<"\n";
        for(int i=0;i<rebra[fron].size();i++){
            if(prin[rebra[fron][i].x]!=prin[fron]) continue;
            int to=rebra[fron][i].x;
            if(!g[to]){
                if(!used[to]){
                    dist[to]=dist[fron]+1;
                    bfs1.push(to);
                }else{
                    dist[to]=dist[fron];
                    bfs.push(to);
                }
                if(dist[to]>=mxdist){
                    mxdist=dist[to];
                    mxi=to;
                }
                g[to]=true;
                par[to]=fron;
            }else{
                bool da=false;
                int nzd=par[fron];
                while(nzd!=curr){
                    if(to==nzd){
                        da=true;
                        break;
                    }
                    nzd=par[nzd];
                }
                if(to==curr) continue;
                if(da) continue;
                if(dist[par[to]]<dist[fron]){
                    dist[to]-=dist[par[to]];
                    dist[to]+=dist[fron];
                    par[to]=fron;
                    if(dist[to]>=mxdist){
                        mxdist=dist[to];
                        mxi=to;
                    }
                }
            }
        }
    }
    if(mxdist==0) return curr;
    //if(nextd) dayind++;
    int y=mxi,ind=0;
    while(y!=curr){
        obh[ind]=y;
        ind++;
        y=par[y];
    }
    for(int i=ind-1;i>=0;i--){
        addtopath(obh[i]);
        if(done) break;
    }
    return mxi;
}
pair<bool,int> bfsnaob(int curr,int x,bool blockuse){
    queue<int> bfs;
    int y,sz;
    for(int i=0;i<=n;i++){
        par[i]=0;
        globalg[i]=false;
    }
    bfs.push(x);
    globalg[x]=true;
    /*if(curr==x){
       // cout<<curr<<" z "<<x<<" "<<dayind<<"\n";
        return true;
    }*/
    bool sv=false;
    while(!bfs.empty() && !sv){
        int fron=bfs.front();
      //  cout<<"vlizam "<<fron<<"\n";
        bfs.pop();
        for(int i=0;i<rebra[fron].size();i++){
            if(!globalg[rebra[fron][i].x]){
                if(blockuse && gg[rebra[fron][i].x]) continue;
              //  if(!davz || (davz && !used[rebra[fron][i].x]))
                if(prin[rebra[fron][i].x]!=prin[fron]){
                    if(prin[rebra[fron][i].x]!=curr) continue;
                    else{
                        bfs.push(rebra[fron][i].x);
                        par[rebra[fron][i].x]=fron;
                        return {true,rebra[fron][i].x};
                    }
                }
                bfs.push(rebra[fron][i].x);
                globalg[rebra[fron][i].x]=true;
                par[rebra[fron][i].x]=fron;
            }
        }
    }
    return {false,0};
}
int fillsubtree(int curr,int cur1){
    int cc=deqbfs(curr,false);
    while(cc!=curr){
      //  cout<<"\n"<<cc<<" "<<curr<<"vlizam\n";
        curr=cc;
        cc=deqbfs(curr,true);
  //  if(startnode==5 && cur1==5) cout<<done<<"zz\n";
        if(done) return curr;
       // cout<<cc<<" "<<curr<<"izlizam\n";
    }
    for(int i=1;i<=n;i++){
        par[i]=0;
    }
    if(cur1==-1) return cur1;
    pair<bool,int> ass=bfsnaob(cur1,curr,true);
    if(!ass.first) ass=bfsnaob(cur1,curr,false);
    int y=ass.second,ind=0;
    while(y!=curr){
      //  cout<<y<<" da "<<curr<<"\n";
        obh[ind]=y;
        ind++;
        y=par[y];
    }
    for(int i=ind-1;i>=1;i--){
      //  cout<<obh[i]<<" ";
        addtopath(obh[i]);
        if(done) break;
    }
    return ass.second;
}
void prestigebfs(int x){
    queue<int> bfs;
    bfs.push(x);
    int broqch=0;
    g[x]=true;
    while(!bfs.empty()){
        int fron=bfs.front();
        realst[fron]=broqch;
        broqch++;
        bfs.pop();
        for(int i=0;i<vrebra[fron].size();i++){
            if(!g[vrebra[fron][i]]){
                bfs.push(vrebra[fron][i]);
                g[vrebra[fron][i]]=true;
            }
        }
    }
    return;
}
int broqch=0,lst=0;
bool ima=false;
int testdfs(int x,int p){
    g[x]=true;
    par[x]=p;
    broqch++;
    int istbroqch=broqch,ans=x;
    for(int i=0;i<rebra[x].size();i++){
        if(g[rebra[x][i].x]) continue;
        ans=testdfs(rebra[x][i].x,x);
        if(broqch==n){
            ima=true;
            lst=ans;
        }
        broqch=0;
    }
    return ans;
}
long long currmin=LLONG_MAX;
int nach=6,mnoj=31;
int currmini=1;
pair<int,int> currmass[5*MAXN];
int curr;
pair<int,int> rebs[MAXN*5];
void dfsdurv(int x,int p){
    //x=prin[curr];
  //  cout<<"\n"<<startnode<<" "<<x<<" "<<curr<<" "<<p<<"\n";
    if(done && x!=prin[startnode]) return;
    addtopath(curr);
    durvg[x]=true;
    int minu=1;
   // cout<<"vlizam\n";
    if(p==-1) minu--;
    int cur1=curr;
    minu=durvreb[x].size()-minu;
  //  if(startnode!=1) cout<<minu<<" "<<curr<<"\n";
    for(int i=0;true;i++){
      //  if(startnode!=1) cout<<curr<<"\n";
        int to=findpath(curr,p);
        if(to==-1) break;
       // cout<<"yo\n";
    //if(startnode!=1) cout<<"vlizam\n";
        if(done) break;
        curr=durvreb[x][to].sty;
        dfsdurv(durvreb[x][to].x,x);
        if(done) break;
        addtopath(curr);
        // cout<<curr<<" ";
    }
    //if(startnode==5) cout<<"izlizam "<<" "<<x<<" "<<curr<<" "<<p<<"\n";;
    if(!done) curr=fillsubtree(curr,p);
  //  if(startnode==5) cout<<"zlizam "<<curr<<"\n";;
   // if(minu==0) dayind++;
    if(x==prin[startnode]){
        long long minn=LLONG_MAX-1;
        int mini=1,koe=0;
        int ds=day.size(),dind=0,dok=min(n,10000000/n);
        for(int i=1;i<=dok;i++){
            //time(&endd);
            //double timetaken=double(endd-start)/double(CLOCKS_PER_SEC);
            //if(timetaken>3) break;
            for(int i1=1;i1<=n;i1++){
                g[i1]=false;
            }
            long long myscore=0,myscore1=0;
            prestigebfs(i);
            for(int i1=1;i1<ds;i1++){
                myscore+=(st[realst[day[i1]]]-st[realst[day[i1-1]]])*(st[realst[day[i1]]]-st[realst[day[i1-1]]]);
                myscore1+=(st1[realst[day[i1]]]-st1[realst[day[i1-1]]])*(st1[realst[day[i1]]]-st1[realst[day[i1-1]]]);
            }
            if(myscore<myscore1){
                if(myscore<minn){
                    minn=myscore;
                    mini=i;
                    koe=0;
                }
            }else{
                if(myscore1<minn){
                    minn=myscore1;
                    mini=i;
                    koe=1;
                }
            }
        }
        for(int i1=1;i1<=n;i1++){
            g[i1]=false;
        }
       // cout<<mini<<"\n";
        prestigebfs(mini);
       // cout<<minn<<"\n";
        for(int i=1;i<=n;i++){
            if(finall){
                if(koe==0) cout<<st[realst[i]]<<" ";
                else if(koe==1) cout<<st1[realst[i]]<<" ";
            }
            globalg[i]=false;
        }
        if(finall) cout<<"\n";
        for(int i=0;i<ds;i++){
            if(globalg[day[i]]){
                dind++;
                for(int i1=1;i1<=n;i1++){
                    globalg[i1]=false;
                }
                globalg[day[i-1]]=true;
            }
            globalg[day[i]]=true;
            dayind[dind]++;
        }
        bool da=false;
        minn=minn*(dind+1);
        if(minn<currmin){
            currmin=minn;
            for(int i=0;i<m;i++){
                currmass[i]=rebs[i];
            }
            currmini=startnode;
            /*if(minn<270092773549 && n>20){
                finall=true;
                for(int i=1;i<=n;i++){
                    cout<<st[realst[i]]<<" ";
                }
                cout<<"\n";
            }*/
        }
        if(finall){
            cout<<dind+1<<"\n";
            int broqch=0;
            for(int i=0;i<=dind;i++){
                ds=dayind[i];
             //   if(i==dind && day.size()>1 && day[day.size()-1]==startnode && !da) ds--;
                if(i==0) cout<<ds<<" ";
                else cout<<ds+1<<" "<<day[broqch-1]<<" ";
                for(int i1=0;i1<ds;i1++){
                    cout<<day[broqch]<<" ";
                    broqch++;
                }
                cout<<"\n";
            }
        }
    }
    return;
}
hamnode dp[20][(1<<15)];
bool rebex[20][20];
bool Hamiltonian_path(){
    for (int i=0;i<n;i++) dp[i][(1<<i)].imali=true;
    for (int i=0;i<(1<<n);i++) {
        for (int i1=0;i1<n;i1++) {
            if (i&(1<<i1)) {
                for (int k=0;k<n;k++) {
                    if (i&(1<<k) && rebex[k][i1] && i1!=k && dp[k][i^(1<<i1)].imali){
                        dp[i1][i].imali=true;
                        dp[i1][i].prev=k;
                        dp[i1][i].prevmask=i^(1<<i1);
                        break;
                    }
                }
            }
        }
    }
    for (int i=0;i<n;i++) {
        int ind=i,mask=(1<<n)-1;
        bool vl=false;
        while(dp[ind][mask].imali){
            day.push_back(ind);
            realst[ind]=realstind;
            realstind++;
            vl=true;
            int z=ind;
            ind=dp[ind][mask].prev;
            if(ind==-1) break;
            mask=dp[z][mask].prevmask;
        }
        if(vl){
            for(int i=0;i<n;i++){
                cout<<st[realst[i]-1]<<" ";
            }
            cout<<"\n";
            cout<<1<<"\n";
            int dsss=day.size();
            cout<<dsss<<" ";
            for(int i=0;i<dsss;i++){
                cout<<day[i]+1<<" ";
            }
            cout<<"\n";
            return true;
        }
    }
    return false;
}
int preds[MAXN],regizh[1001][1001],isprin[MAXN];
int main(){
    freopen("taxi.in","r",stdin);
    freopen("taxi.out","w",stdout);
    time(&start);
    srand(nach);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>st[i];
        st1[i]=st[i];
    }
    sort(st,st+n);
    sort(st1,st1+n,greater<int>());
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        node n1,n2;
        n1.x=y;
        n2.x=x;
        rebs[i]={x,y};
        rebra[x].push_back(n1);
        rebra[y].push_back(n2);
        x--;
        y--;
        if(n<=20){
            rebex[x][y]=true;
            rebex[y][x]=true;
        }
    }
   // cout<<"vlizam\n";
   if(n>15 || !Hamiltonian_path()){
        dfsmst(1,-1,-1);
        for(int i=1;i<=n;i++){
            g[i]=false;
        }
        int ind=1;
        for(int i=1;i<=n;i++){
            if(!g[i]){
                dfs(i,ind,i);
                ind++;
            }
        }
        int indd=1;
        for(int i=1;i<=n;i++){
            if(isprin[prin[i]]==0){
                isprin[prin[i]]=indd;
                preds[indd]=i;
                indd++;
            }
            prin[i]=isprin[prin[i]];
            //cout<<i<<": "<<prin[i]<<"\n";
        }
        random_shuffle(rebs,rebs+m);
        for(int i=0;i<m;i++){
            int x=prin[rebs[i].first],y=prin[rebs[i].second];
            if(x==y) continue;
      //      cout<<"vlazqm "<<rebs[i].first<<" "<<rebs[i].second<<" "<<x<<" "<<y<<"\n";
            durvnode dn1,dn2;
            dn1.x=y;
            dn1.stx=rebs[i].first;
            dn1.sty=rebs[i].second;
            dn2.x=x;
            dn2.sty=rebs[i].first;
            dn2.stx=rebs[i].second;
            durvreb[x].push_back(dn1);
            durvreb[y].push_back(dn2);
            if(n<=1000){
                regizh[dn1.stx][y]=durvreb[x].size()-1;
                regizh[dn2.stx][x]=durvreb[y].size()-1;
            }
            izh[dn1.stx].push_back({y,durvreb[x].size()-1});
            izh[dn2.stx].push_back({x,durvreb[y].size()-1});
        }
      /*  int minn=INT_MAX,mini;
        for(int i=1;i<=mstind+1;i++){
            int is=durvreb[i].size();
            if(is<=minn){
                minn=is;
                mini=i;
            }
        }*/
        int q=200;
      //  currmini=rand()%n+1;
        if(n<=1000){
            int z=n,pll=1;
            if(n>100){
                q=1;
                z=150;
                pll=n/z;
            }
            for(int i2=1;i2<=q;i2++){
                srand(i2*mnoj+nach);
                for(int i0=1;i0<=n;i0+=pll){
                    startnode=i0;
                    curr=startnode;
                    int qq=testdfs(startnode,-1);
                    if(ima){
                        int x=lst;
                        while(x!=-1){
                            addtopath(x);
                            x=par[x];
                        }
                        for(int i=0;i<n;i++){
                            cout<<st[realst[i+1]-1]<<" ";
                        }
                        cout<<"\n1\n"<<n<<" ";
                        for(int i=0;i<n;i++){
                            cout<<day[i]<<" ";
                        }
                        cout<<"\n";
                        return 0;
                    }
                    lst=0;
                    broqch=0;
                    for(int i=0;i<=n;i++){
                        g[i]=false;
                        par[i]=0;
                    }
                    dfsdurv(prin[startnode],-1);
                    if(finall) return 0;
                    //cout<<"vlizam\n";
                 //   cout<<"vlizam\n";
                    day.clear();
                    done=false;
                    daysz=0;
                    for(int i=0;i<=n;i++){
                        vrebra[i].clear();
                        dayind[i]=0;
                        realst[i]=0;
                        realstind=1;
                        globalg[i]=false;
                        used[i]=false;
                        gg[i]=false;
                        g[i]=false;
                        par[i]=0;
                        durvg[i]=false;
                        obh[i]=0;
                    }
                    if(i2==q && i0==n){
                        for(int i=0;i<m;i++){
                            rebs[i]=currmass[i];
                        }
                    }else random_shuffle(rebs,rebs+m);
                    for(int i=0;i<m;i++){
                        int x=prin[rebs[i].first],y=prin[rebs[i].second];
                        if(x==y) continue;
                        durvnode dn1,dn2;
                        dn1.x=y;
                        dn1.stx=rebs[i].first;
                        dn1.sty=rebs[i].second;
                        dn2.x=x;
                        dn2.sty=rebs[i].first;
                        dn2.stx=rebs[i].second;
                        izh[dn1.stx].push_back({y,regizh[dn1.stx][y]});
                        izh[dn2.stx].push_back({x,regizh[dn2.stx][x]});
                    }
                }
            }
        }
        //cout<<(currmint-nach)/mnoj<<"\n";
        finall=true;
        startnode=currmini;
        int qq=testdfs(startnode,-1);
        if(ima){
            int x=lst;
            while(x!=-1){
                addtopath(x);
                x=par[x];
            }
            for(int i=0;i<n;i++){
                cout<<st[realst[i+1]-1]<<" ";
            }
            cout<<"\n1\n"<<n<<" ";
            for(int i=0;i<n;i++){
                cout<<day[i]<<" ";
            }
            cout<<"\n";
            return 0;
        }
        lst=0;
        broqch=0;
        for(int i=0;i<=n;i++){
            g[i]=false;
            par[i]=0;
        }
        curr=startnode;
        dfsdurv(prin[startnode],-1);
      //  cout<<currmin<<"\n";
   }
    return 0;
}