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

#define MAX_CITIES 100000
#define MAX_PATH 1000000
#define MAX_DAYS 100000
int n, m;
int s[MAX_CITIES+1];
vector<int> adj[MAX_CITIES+1];
int path[MAX_PATH], path_count;
int visits[MAX_CITIES+1];
int vorder[MAX_CITIES+1];
int visited_count;
int cur_day;
vector <tuple<int, int, int>> swaps;
int explore_level;

long long sol_cost;
bool sol_asc;
int sol_days;
int sol_length;
int sol_path[MAX_PATH+1], sol_path_count;
int prestige[MAX_CITIES+1];

chrono::high_resolution_clock::time_point start_time;

void init() {
  path_count = 0;
  visited_count = 0;
  cur_day = 1;
  for(int c=1; c<=n; c++) visits[c]=0;
}

void print() {
  for(int c=1; c<n; c++) cout << prestige[c] << " ";
  cout << prestige[n] << endl;
  cout << sol_days << endl;
  int pi = 0;
  for(int id=1; id<=sol_days; id++) {
    int num_cities = 1;
    while(pi + 1 < sol_path_count && sol_path[pi] != sol_path[pi+1]) {
      pi++; num_cities++;
    }
    cout << num_cities << " ";
    for(int j=1; j<=num_cities; j++) cout << sol_path[pi-num_cities+j] << " "; cout << endl;
    pi++;
  }
}

void check_solution() {
  int new_solution = 0;
  long long cost = 0, added, cutoff = sol_cost / cur_day;

  int u = path[0]; int v;

  for(int i=1; i<path_count; i++) {
    v = path[i];
    added = ((long long)s[vorder[u]] - s[vorder[v]]) * (s[vorder[u]] - s[vorder[v]]);
    if (cost > LLONG_MAX - added || cost > cutoff) {
      cost = -1;
      break;
    } else {
      cost += added;
    }
    u = v;
  }

  if (cost > 0) {
    if (cost > LLONG_MAX / cur_day) {
      cost = -1;
    } else {
      cost *= cur_day;
    }
  }

  if (cost > 0 && cost < sol_cost) {
    sol_cost = cost;
    sol_length = path_count;
    new_solution = 1;
    cutoff = sol_cost / cur_day;
  }

  cost = 0;
  u = path[0];
  for(int i=1; i<path_count; i++) {
    v = path[i];
    added = ((long long)s[n+1-vorder[u]] - s[n+1-vorder[v]]) * (s[n+1-vorder[u]] - s[n+1-vorder[v]]);
    if (cost > LLONG_MAX - added || cost > cutoff) {
      cost = -1;
      break;
    } else {
      cost += added;
    }
    u = v;
  }

  if (cost > 0) {
    if (cost > LLONG_MAX / cur_day) {
       cost = -1;
    } else {
       cost *= cur_day;
    }
  }

  if (cost > 0 && cost < sol_cost) {
    sol_cost = cost;
    sol_length = path_count;
    new_solution = 2;
  }

  if (new_solution != 0) {
    sol_days = cur_day;
    sol_path_count = path_count;
    for(int i=0; i<path_count; i++) sol_path[i] = path[i];
    if (new_solution == 1) {
      for(int c=1; c<=n; c++) {
        prestige[c] = s[vorder[c]];
      }
    } else {
      for(int c=1; c<=n; c++) {
        prestige[c] = s[n+1-vorder[c]];
      }
    }
  }
}

void undo(int until_path_count) {
  while (path_count != until_path_count) {
    visits[path[--path_count]]--;
  }
}
int explore_optimized(int city) {
  int returns = 0;
  visited_count++;
  visits[city]++;
  path[path_count++] = city;
  vorder[city] = visited_count;
  if (path_count >= MAX_PATH) return true;
  if (visited_count == n) {
    check_solution();
    return 0;
  }
  bool deadend = true;
  int continued = 0;
  int prev_i = -1, prev_edge_returns = 0, prev_path_count = path_count, prev_cur_day = cur_day, prev_visited_count = visited_count, prev_returns = returns;
  for(int i = 0; i < adj[city].size(); i++) {
    int next_city = adj[city][i];
    if (visits[next_city] != 0) continue;

    deadend = false;
    if (++continued > 1) returns++;
    int saved_path_count = path_count, saved_cur_day = cur_day, saved_visited_count = visited_count, saved_returns = returns;
    int edge_returns = explore_optimized(next_city);
    if (continued > 1 && edge_returns < prev_edge_returns) {
      swap(adj[city][i], adj[city][prev_i]);
      swaps.push_back({city, i, prev_i});
      undo(prev_path_count);
      continued-=2;
      cur_day = prev_cur_day;
      visited_count = prev_visited_count;
      returns = prev_returns;
      i = prev_i-1;
      prev_i = -1, prev_edge_returns = 0, prev_path_count = path_count, prev_cur_day = cur_day, prev_visited_count = visited_count; prev_returns = returns;
      continue;
    } else {
      prev_i = i; prev_edge_returns = edge_returns;
      prev_path_count = saved_path_count; prev_cur_day = saved_cur_day; prev_visited_count = saved_visited_count;
      prev_returns = saved_returns;
    }
    returns += edge_returns;
    if (visited_count == n) return returns;

    visits[city]++;
    path[path_count++] = city;
  }
  if (deadend) {
    cur_day++;
    visits[city]++;
    path[path_count++] = city;
  }
  return returns;
}

void undo_swaps() {
  for(int i=0; i<swaps.size(); i++) {
    int city = get<0>(swaps[i]);
    swap(adj[city][get<1>(swaps[i])], adj[city][get<2>(swaps[i])]);
  }
}


int explore_returns(int city, int level) {
  if (level == explore_level) return adj[city].size() * 2; // 2
  int returns = 2;
  visits[city]++;
  int continued = 0;
  for (int i = 0; i < adj[city].size(); i++) {
    int next_city = adj[city][i];
    if (visits[next_city] == 0) {
      returns += explore_returns(next_city, level+1);
      continued++;
    }
  }
  if (continued > 1) returns += (continued-1);
  visits[city]--;
  return returns;
}


bool explore_sorted(int city) {
  visited_count++;
  visits[city]++;
  path[path_count++] = city;
  vorder[city] = visited_count;
  if (path_count >= MAX_PATH) return true;
  if (visited_count == n) {
    check_solution();
    return true;
  }
  bool deadend = true;
  vector <pair<int, int>> new_order;
  for(int i = 0; i < adj[city].size(); i++) {
    int next_city = adj[city][i];
    if (visits[next_city] != 0) continue;
    new_order.push_back({explore_returns(next_city, 1), next_city});
  }
  sort(new_order.begin(), new_order.end());
  if (new_order.size() > 0) {
    for(int i = 0; i < new_order.size(); i++) {
      int next_city = new_order[i].second;
      if (visits[next_city] == 0) {
        deadend = false;
        if(explore_sorted(next_city)) return true;
        visits[city]++;
        path[path_count++] = city;
        if (path_count >= MAX_PATH) return true;
      }
    }
  }
  if (deadend) {
    cur_day++;
    visits[city]++;
    path[path_count++] = city;
    if (path_count >= MAX_PATH) return true;
  }
  return false;
}

bool explore_fastest(int city) {
  visited_count++;
  visits[city]++;
  path[path_count++] = city;
  vorder[city] = visited_count;
  if (path_count >= MAX_PATH) return true;
  if (visited_count == n) {
    check_solution();
    return true;
  }
  int children = 0;
  for(int i = 0; i < adj[city].size(); i++) {
    int next_city = adj[city][i];
    if (visits[next_city] == 0) {
      children++;
      if(explore_fastest(next_city)) return true;
      visits[city]++;
      path[path_count++] = city;
      if (path_count >= MAX_PATH) return true;
    }
  }
  if (children == 0) {
    cur_day++;
    visits[city]++;
    path[path_count++] = city;

    if (path_count >= MAX_PATH) return true;
  }
  return false;
}

void solve() {
  int strategy = 0;
  if (n >= 50 && n <= 450) strategy = 1;
  if (n * 1.1 > m) explore_level = 20; else explore_level = 5;
  if (n > 50000) strategy = 2;
  sol_cost = LLONG_MAX;
  sol_days = MAX_DAYS;
  sol_length = MAX_PATH;
  for(int v=1; v<=n; v++) {
    if (adj[v].size() == 2 && (adj[adj[v][0]].size() == 2 && adj[adj[v][1]].size() == 2)) continue;
    init();
    switch (strategy) {
      case 0:
        explore_optimized(v);
        if (n < 100) {
          undo_swaps();
        }
        swaps.clear();
        break;
      case 1:
        explore_sorted(v);
        break;
      case 2:
        explore_fastest(v);
        break;
    }
    chrono::high_resolution_clock::time_point cur_time = chrono::high_resolution_clock::now();
    if ((cur_time - start_time) / 1ms > 4500) break;
  }
}

int main() {
  start_time = chrono::high_resolution_clock::now();
  freopen("taxi.in", "r", stdin);
  freopen("taxi.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i=1; i<=n; i++) cin >> s[i];
  sort(s+1, s+n+1);
  for(int i=0; i<m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  solve();
  print();
}