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

const int MAXN = 100005;

struct Edge {
    int u, v;
};

vector<int> adj[MAXN];
bool visited[MAXN];
vector<int> path;

int dfs(int u, int n) {
    visited[u] = true;
    path.push_back(u);

    if (path.size() == n) {
        return true;
    }

    for (int v : adj[u]) {
        if (!visited[v]) {
            if (dfs(v, n)) {
                return true;
            }
        }
    }

    visited[u] = false;
    path.pop_back();
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // Input and file redirection
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    vector<int> prestige_vals(n);
    vector<pair<int, int>> degree_prestige(n);
    for (int i = 0; i < n; ++i) {
        cin >> prestige_vals[i];
        degree_prestige[i] = {0, i};
    }

    // Sort prestige values for later assignment
    sort(prestige_vals.begin(), prestige_vals.end(), greater<int>());

    vector<Edge> edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u - 1, v - 1});
        degree_prestige[u-1].first++;
        degree_prestige[v-1].first++;
    }

    // Sort by degree and assign prestige
    sort(degree_prestige.begin(), degree_prestige.end(), greater<pair<int, int>>());
    vector<int> final_prestige(n);
    for (int i = 0; i < n; ++i) {
        final_prestige[degree_prestige[i].second] = prestige_vals[i];
    }

    // Rebuild the graph with the assigned prestige
    for (auto &e : edges) {
        int cost = pow(final_prestige[e.u] - final_prestige[e.v], 2);
        adj[e.u].push_back(e.v);
        adj[e.v].push_back(e.u);
    }

    // Output prestige values
    for (int i = 0; i < n; ++i) {
        cout << final_prestige[i] << " ";
    }
    cout << endl;

    // Find path using DFS
    dfs(0, n);

    // Output the path
    cout << 1 << endl; // Assume the taxi takes 1 day to visit all cities
    cout << n << " ";
    for (int city : path) {
        cout << city + 1 << " ";
    }
    cout << endl;

    return 0;
}