#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<int,int> pii;
typedef pair<short,short> pss;
typedef pair<short,int> psi;

/// INIT
const int maxn=3e5+10;
int n,m;
vector<int>vect[maxn];
vector<ll> s;
/// INIT END

struct dsu{

    int n;
    int cc;
    vector<int>p,sz;

    dsu(int n){
        this->n=n;
        this->cc=n;
        p.resize(n+1);
        sz.resize(n+1);
        for(int i=1;i<=n;i++){
            p[i]=i;
            sz[i]=1;
        }
    }

    void reset(){
        for(int i=1;i<=n;i++){
            p[i]=i;
            sz[i]=1;
        }
        cc=n;
    }
    int root(int x){
        if(p[x]==x)return x;
        return p[x]=root(p[x]);
    }
    bool join(int u,int v){
        u=root(u);
        v=root(v);
        if(u==v)return false;
        if(sz[u]>sz[v])swap(u,v);
        p[u]=v;
        sz[v]+=sz[u];
        cc--;
        return true;
    }

};

ll inf=1e18;
int intinf=1e9;
struct result{

    int n;
    vector<vector<int>>paths;
    vector<ll>p;
    vector<bool>pos;
    ll score=-1;

    result(int n){
        this->n=n;
        pos.resize(n,0);
    }

    void add_path(vector<int>&v){
        paths.pb(v);
    }
    void add_to_last_path(int x){
        if(paths.size()==0)assert(1==0);
        paths.back().pb(x);
    }
    void new_path(){
        paths.pb(vector<int>());
    }
    void assign_p(vector<ll>np){
        p=np;
    }

    void calc_score(){
        if(p.size()!=n){
            printf("%d %d AAA\n",p.size(),n);
            assert(1==0);
        }
        for(int i=0;i<n;i++)pos[i]=false;

        score=0;
        for(int i=0;i<paths.size();i++){
            for(int j=1;j<paths[i].size();j++){
                int id=paths[i][j-1];
                int id2=paths[i][j];
                score+=(p[id2]-p[id])*(p[id2]-p[id]);
                if(score>inf)score=inf;
            }
        }

        if(score>inf/paths.size())score=inf;
        else score*=paths.size();

    }

    void ispis(){
        for(int i=0;i<p.size();i++)printf("%d ",p[i]);
        printf("\n");
        printf("%d\n",paths.size());
        for(int i=0;i<paths.size();i++){
            printf("%d ",paths[i].size());
            for(int j=0;j<paths[i].size();j++)printf("%d ",paths[i][j]+1);
            printf("\n");
        }
    }

    bool operator <(const result &r) const{
        return score<r.score;
    }

};



result complete_trinary_bitmasks(){

    /// dp[mask][i] - mask with trits, last vertex is i
    /// moras dijkstru raditi

    int pw3[n+1];
    pw3[0]=1;
    for(int i=1;i<=n;i++)pw3[i]=pw3[i-1]*3;

    int niz[n],pom;
    vector<vector<pii>>dp(pw3[n],vector<pii>(n,(pii){intinf,intinf})),par(pw3[n],vector<pii>(n,(pii){-1,-1}));

    queue<pair<pii,pii>>st[2];
    for(int i=0;i<n;i++){
        dp[0][i]={0,0};
        dp[pw3[i]][i]={1,0};
        st[0].push( {{1,0},{pw3[i],i}} );
    }

    pii end_state={-1,-1};
    while(st[0].size() || st[1].size()){

        /// get min
        pii a,b;
        int wq=0;
        if(st[0].size()==0){
            wq=1;
        }
        else if(st[1].size()==0){
            wq=0;
        }
        else{
            a=st[0].front().ss;
            b=st[1].front().ss;
            if(dp[a.ff][a.ss]<dp[b.ff][b.ss])wq=0;
            else wq=1;
        }
        /// end get min


        pii x=st[wq].front().ss;
        int u=x.ss;
        int mask=x.ff;
        if(st[wq].front().ff!=dp[x.ff][x.ss]){
            st[wq].pop();
            continue;
        }
        st[wq].pop();


        pom=mask;
        int ee=1;
        for(int i=0;i<n;i++){
            niz[i]=pom%3;
            pom/=3;
            if(niz[i]==0)ee=0;
        }

        if(ee){
            //if(end_state.ff==-1)
                end_state=x;
            break;
        }

        int nxt=mask;
        pii w={1,0};
        for(int j=0;j<n;j++){
            if(j==u)continue;
            if(niz[j]==1)nxt+=pw3[j];
        }
        if(dp[nxt][u]>(pii){dp[mask][u].ff+w.ff,dp[mask][u].ss+w.ss}){
            ///st.erase({dp[nxt][u],{nxt,u} });
            dp[nxt][u]={dp[mask][u].ff+w.ff,dp[mask][u].ss+w.ss};
            par[nxt][u]={mask,u};
            st[0].push({dp[nxt][u],{nxt,u} });
        }

        for(int i=0;i<vect[u].size();i++){

            int id=vect[u][i];
            w={0,1};

            if(niz[id]==1){
                continue;
            }
            else if(niz[id]==0){
                nxt=mask+pw3[id];
            }
            else{
                nxt=mask-pw3[id];
            }

            if(dp[nxt][id]>(pii){dp[mask][u].ff+w.ff,dp[mask][u].ss+w.ss}){
                //st.erase({dp[nxt][id],{nxt,id} });
                dp[nxt][id]={dp[mask][u].ff+w.ff,dp[mask][u].ss+w.ss};
                par[nxt][id]={mask,u};
                st[1].push({dp[nxt][id],{nxt,id} });
            }

        }

    }


    result ret(n);

    pii curr=end_state;
    int prvd=-1;
    while(curr!=(pii){-1,-1}){
        if(prvd!=dp[curr.ff][curr.ss].ff)ret.new_path();
        ret.add_to_last_path(curr.ss);
        prvd=dp[curr.ff][curr.ss].ff;
        curr=par[curr.ff][curr.ss];
    }

    return ret;

}

namespace bitmask_dp{

short short_inf=30000;

template<typename T>
void check_if_have_to_resize(T &a,int n){

    if(a.size()<n)a.resize(n);
    for(int i=0;i<n;i++)
        if(a[i].size()<(1<<n))a[i].resize(1<<n);

}
vector<int>recover_path(int mask,short u,vector<vector<pair<short,int>>>&par){
    vector<int>ret;
    while(mask!=-1){
        ret.pb(u);
        pii pom=par[u][mask];
        mask=pom.ss;
        u=pom.ff;
    }
    reverse(ret.begin(),ret.end());
    return ret;
}
vector<pair<pii,vector<int>>> get_non_intersecting_path(vector<int>start_points,vector<int>taken_nodes,int k,
                                                        vector<vector<pair<short,short>>>&dp,vector<vector<pair<short,int>>>&par){

    check_if_have_to_resize(dp,n);
    check_if_have_to_resize(par,n);

    /*printf("START POINTS\n");
    for(int i=0;i<start_points.size();i++)printf("%d ",start_points[i]);
    printf("\ntaken POINTS\n");
    for(int i=0;i<taken_nodes.size();i++)printf("%d ",taken_nodes[i]);
    printf("\n");*/


    for(int i=0;i<n;i++){
        for(int j=0;j<(1<<n);j++){
            dp[i][j]={short_inf,short_inf};
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<(1<<n);j++){
            par[i][j]={-1,-1};
        }
    }

    vector<int>node_price(n,1);
    for(int i=0;i<taken_nodes.size();i++)
        node_price[taken_nodes[i]]=0;

    for(int i=0;i<start_points.size();i++){
        int id=start_points[i];
        dp[id][1<<id]={-node_price[id],0};
    }

    for(int mask=0;mask<(1<<n);mask++){

        for(int i=0;i<n;i++){
            if(dp[i][mask].ff==short_inf)continue;

            for(int j=0;j<vect[i].size();j++){
                int id=vect[i][j];
                if(mask&(1<<id))continue;

                pair<short,short>w={-node_price[id],1};

                if(dp[id][mask|(1<<id)]>(pss){dp[i][mask].ff+w.ff,dp[i][mask].ss+w.ss}){
                    dp[id][mask|(1<<id)]={dp[i][mask].ff+w.ff,dp[i][mask].ss+w.ss};
                    par[id][mask|(1<<id)]={i,mask};
                }

            }

        }

    }



    set<pair<pss,psi>>st;
    for(int mask=(1<<n)-1;mask>=0;mask--){
        for(int i=0;i<n;i++){
            if(dp[i][mask].ff==short_inf)continue;

            if(st.size()<k){
                st.insert({dp[i][mask],{i,mask}});
                continue;
            }
            pss lst=(*st.rbegin()).ff;
            if(dp[i][mask]>lst)continue;
            psi pom=(*st.rbegin()).ss;

            st.insert({dp[i][mask],{i,mask}});
            st.erase({lst,pom});
        }
    }



    vector<pair<pii,vector<int>>>ret;
    for(auto it=st.begin();it!=st.end();it++){
        vector<int>path=recover_path((*it).ss.ss,(*it).ss.ff,par);
        pii pom;
        pom.ff=(*it).ff.ff;
        pom.ss=(*it).ff.ss;
        ret.pb({pom,path});
    }

    return ret;

}

result solve_with_greedy_bitmasks(){

    int max_result=1;

    vector<vector<pair<short,short>>>dp;
    vector<vector<pair<short,int>>>par;

    vector<pair<pii,pair<vector<int>,result>>>ret,ret2;


    vector<int>sp(n);
    for(int i=0;i<n;i++)sp[i]=i;
    result r(n);
    ret.pb({ {0,0} , {sp,r} });
    while(ret[0].ff.ff!=-n){

        for(int i=0;i<ret.size();i++){

            vector<int>taken_nodes;
            result pr=ret[i].ss.ss;
            for(int j=0;j<pr.paths.size();j++)
                for(int k=0;k<pr.paths[j].size();k++)
                    taken_nodes.pb(pr.paths[j][k]);


            //printf("DOSAO\n");
            vector<pair<pii,vector<int>>>paths=get_non_intersecting_path(ret[i].ss.ff,taken_nodes,5,dp,par);
            //printf("DOSAO222\n");

            for(auto path:paths){

                pii pom=ret[i].ff;
                pom.ff+=path.ff.ff;
                pom.ss+=path.ff.ss;

                vector<int>sp;
                sp.pb(path.ss.back());
                pr.add_path(path.ss);

                ret2.pb({pom,{sp,pr} });
                /*printf("%d %d POM\n",pom.ff,pom.ss);
                for(int j=0;j<path.ss.size();j++)printf("%d ",path.ss[j]);
                printf(" PATH\n");*/
            }

        }

        sort(ret2.begin(),ret2.end());
        while(ret2.size()>max_result)ret2.pop_back();
        ret=ret2;

    }

    ///printf("%d %d AAAA RET\n",ret[0].ff.ff,ret[0].ff.ss);
    return ret[0].ss.ss;
}

}

result assign_result(){
    result r(n);
    if(n>11)r=bitmask_dp::solve_with_greedy_bitmasks();
    else r=complete_trinary_bitmasks();

    return r;
}

void all_permutations_assignment(result &r){
    int fact=1;
    for(int i=2;i<=n;i++)fact*=i;

    pair<ll,vector<ll>>rez;
    rez.ff=inf+1;
    for(int i=0;i<fact;i++){
        next_permutation(s.begin(),s.end());
        r.assign_p(s);
        r.calc_score();
        pair<ll,vector<ll>>pom;
        pom.ff=r.score;
        pom.ss=s;
        if(r.score<rez.ff)
            rez=pom;
    }

    //printf("%d RZZ\n",rez.ss.size());
    r.assign_p(rez.ss);
}
void random_shuffle_assignment(result &r,int fact){

    pair<ll,vector<ll>>rez;
    rez.ff=inf+1;
    for(int i=0;i<fact;i++){
        random_shuffle(s.begin(),s.end());
        r.assign_p(s);
        r.calc_score();
        pair<ll,vector<ll>>pom;
        pom.ff=r.score;
        pom.ss=s;
        if(r.score<rez.ff)
            rez=pom;
    }

    r.assign_p(rez.ss);
}
void limited_permutations_assignment(result &r,int fact){

    pair<ll,vector<ll>>rez;
    rez.ff=inf+1;
    for(int i=0;i<fact;i++){
        if(i%1000==0)random_shuffle(s.begin(),s.end());
        next_permutation(s.begin(),s.end());
        r.assign_p(s);
        r.calc_score();
        pair<ll,vector<ll>>pom;
        pom.ff=r.score;
        pom.ss=s;
        if(r.score<rez.ff)
            rez=pom;
    }

    //printf("%d RZZ\n",rez.ss.size());
    r.assign_p(rez.ss);
}
void assign_permutation(result &r){

    if(n<=10){

        all_permutations_assignment(r);
        ///limited_permutations_assignment(r,10000000);

    }
    else{

        ///random_shuffle_assignment(r,10000000);
        ///random_shuffle(s.begin(),s.end());
        limited_permutations_assignment(r,10000000);

    }

}

int main(){


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

    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        int aa;
        scanf("%d",&aa);
        s.pb(aa);
    }

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        vect[u].pb(v);
        vect[v].pb(u);
    }


    result ret=assign_result();
    assign_permutation(ret);
    ret.ispis();
    //ret.calc_score();
    //cout<<ret.score<<endl;

    return 0;
}