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

// city structure, contains prestige value and neighbors
struct city {
    int64_t prestige = 0;
    vector<int> neighbors = {};
    int num = 0;
    bool visited_by_taxi = false;
    bool visited_by_taxi_on_day = false;
    bool visited_by_algorithm = false;
};

// cities and prestige value arrays with fixed size
city cities[100050];
int64_t prestige_values[100050];
int n, m;

// sorting function!!!
bool city_neighbor_count_sort(city& a, city& b) {
    return a.neighbors.size() >= b.neighbors.size();
}

// revert back to normal
bool revert_back(city& a, city& b) {
    return a.num < b.num;
}

// get prestige for two cities
inline int64_t get_highway_price(int prestige_a, int prestige_b) {
    int64_t val = (prestige_a - prestige_b);
    return val * val;
}

// see if all cities have been visited
inline bool check_if_alls_visited() {
    for(int i = 1; i < n + 1; i++) {
        if(!cities[i].visited_by_taxi) {
            return false;
        }
    }
    return true;
}

// djikstra algorithm
int starting_city = 0;              // the starting city!
int64_t smallest_price[100050];     // smallest price possible if you start from starting city
int previous_city[100050];          // previous city visited if you used shortest path for that city
int num_city_passed[100050];        // number of cities the city has passed through on the shortest path

void djikstra() {
    // reset everything thats needed
    for(int i = 1; i < n + 1; i++) {
        smallest_price[i] = 100000000000;
        previous_city[i] = -1;
        num_city_passed[i] = 0;
        cities[i].visited_by_algorithm = false;
    }
    smallest_price[starting_city] = 0;
    bool has_anything_at_all = false;
    bool starting_city_already_selected = false;

    // loop!
    while(true) {
        // find city with least price from starting city
        int64_t smallest_current = 100000000000;
        int smallest_current_index = -1;
        for(int i = 1; i < n + 1; i++) {
            if(i == starting_city && starting_city_already_selected == false || smallest_price[i] < smallest_current && cities[i].visited_by_algorithm == false && cities[i].visited_by_taxi_on_day == false) {
                smallest_current = smallest_price[i];
                smallest_current_index = i;
                if(i == starting_city)
                    starting_city_already_selected = true;
            }
        }
        //cout << smallest_current << " " << smallest_current_index << endl;
        if(smallest_current_index == -1) {
            break;
        }

        // find its neighbors and calculate their prices from starting city
        int current_city = smallest_current_index;
        for(int i = 0; i < cities[current_city].neighbors.size(); i++) {
            // make sure it isnt already visited by the taxi on that day!!!!
            if(cities[cities[current_city].neighbors[i]].visited_by_taxi_on_day == true) {
                continue;
            }

            // make sure it has anything at all to like not break stuff
            has_anything_at_all = true;

            // get highway price from current city and neighboring city
            int64_t total_highway_price = get_highway_price(cities[current_city].prestige, cities[cities[current_city].neighbors[i]].prestige) + smallest_price[current_city];

            // see if its smaller than its current price, if it is than good
            if(total_highway_price < smallest_price[cities[current_city].neighbors[i]]) {
                smallest_price[cities[current_city].neighbors[i]] = total_highway_price;
                previous_city[cities[current_city].neighbors[i]] = current_city;
                num_city_passed[cities[current_city].neighbors[i]] = num_city_passed[current_city] + 1;
            }
        }
        cities[current_city].visited_by_algorithm = true;
    }
    if(has_anything_at_all == false) {
        smallest_price[starting_city] = 100000000000;
        num_city_passed[starting_city] = 0;
    }
    //cout << "--------------------" << endl;
    //cout << "starting city: " << starting_city << endl;
    for(int i = 1; i < n + 1; i++) {
        //cout << "city: " << cities[i].num << " | total highway price: " << smallest_price[i] << " | cities passed: " << num_city_passed[i] << " | previous city: " << previous_city[i] << " | bools: " << cities[i].visited_by_taxi << " " << cities[i].visited_by_taxi_on_day << endl;
    }
}

// output stuff
int amount_of_days = 1;
int last_city = -100;
int last_amount_of_days = 0;
vector<string> output_for_every_day;
vector<int> output_stuff_idk_numbers;

int main() {
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
    // n - number of cities
    // m - number of roads
    cin >> n >> m;

    // get list of prestiges to assign to each city
    for(int i = 0; i < n; i++) {
        scanf("%lld", &prestige_values[i]);
        cities[i + 1].num = i + 1;
    }

    // get routes for every city and make every city have a vector of
    // its neighbors
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        cities[a].neighbors.push_back(b);
        cities[b].neighbors.push_back(a);
    }

    // assign prestige values
    sort(cities + 1, cities + n + 1, city_neighbor_count_sort);
    sort(prestige_values, prestige_values + n);
    for(int i = 1; i < n + 1; i++) {
        cities[i].prestige = prestige_values[i - 1];
    }

    // revert back so that the routes dont get messed up
    sort(cities + 1, cities + n + 1, revert_back);
    for(int i = 1; i < n + 1; i++) {
        //cout << "city: " << cities[i].num << " | prestige: " << cities[i].prestige << " | number of neighbours: " << cities[i].neighbors.size() << endl;
    }

    // djikstra stuff
    starting_city = 1;
    int total_price = 0;

    // see if all days have been visited, if not then continue finding best city to go to
    //int iterations = 0;
    while(!check_if_alls_visited()) {
        // get array info from djikstra algorithm (closest path distance, least city passes...)
        djikstra();

        // find best city (must not be visited by taxi already, best city is the one that taxi will go to!)
        int best_city_passes = 0;
        int best_city = -1;
        for(int i = 1; i < n + 1; i++) {
            if(num_city_passed[i] > best_city_passes && cities[i].visited_by_taxi == false || num_city_passed[i] == best_city_passes && smallest_price[i] < smallest_price[best_city] && cities[i].visited_by_taxi == false) {
                best_city_passes = num_city_passed[i];
                best_city = i;
            }
        }
        //cout << "BEST city: " << best_city << " " << best_city_passes << " " << smallest_price[best_city] << endl;
        // reset day! wait for taxi to recharge or something

        // if best city is -1, its not found and we recharge taxi
        if(best_city == -1) {
            amount_of_days++;
            for(int i = 1; i < n + 1; i++) {
                cities[i].visited_by_taxi_on_day = false;
            }
        // else if we found best city, we go backwards until the starting city because we have to output our movements later on
        } else {
            string travelled = "";
            total_price += smallest_price[best_city];
            //cout << "PRICE!!!: " << smallest_price[best_city] << endl;
            int current_city = best_city;
            int asdfkosadfo = 0;
            while(current_city != -1) {
                if(previous_city[current_city] != -1 && previous_city[current_city] != last_city || previous_city[current_city] != -1 && amount_of_days != last_amount_of_days) {
                    if(current_city != best_city) {
                        travelled += " " + to_string(previous_city[current_city]);
                        asdfkosadfo += 1;
                    } else {
                        travelled += " " + to_string(current_city) + " " + to_string(previous_city[current_city]);
                        asdfkosadfo += 2;
                    }
                } else if(previous_city[current_city] == -1 && current_city == best_city) {
                    travelled += " " + to_string(current_city);
                    asdfkosadfo += 1;
                }
                //cout << "going backwards! " << current_city << " "  << previous_city[current_city] << endl;
                cities[current_city].visited_by_taxi = true;
                cities[current_city].visited_by_taxi_on_day = true;
                current_city = previous_city[current_city];
            }
            last_city = best_city;
            last_amount_of_days = amount_of_days;

            // string manipulation stuff
            reverse(travelled.begin(), travelled.end());
            if(output_for_every_day.size() < amount_of_days)
                output_for_every_day.push_back(travelled);
            else
                output_for_every_day[amount_of_days - 1] += travelled;

            if(output_stuff_idk_numbers.size() < amount_of_days)
                output_stuff_idk_numbers.push_back(asdfkosadfo);
            else
                output_stuff_idk_numbers[amount_of_days - 1] += asdfkosadfo;
            starting_city = best_city;
        }
        //iterations++;
    }

    // OUTPUT
    // prestige of all cities, amount of days spent, taxi movement order
    //cout << "OUTPUT, WE DONT CARE ABOUT THIS MOSTLY." << endl;
    for(int i = 1; i < n + 1; i++) {
        cout << cities[i].prestige << " ";
    }
    cout << '\n' << amount_of_days << '\n';
    for(int i = 0; i < output_for_every_day.size(); i++) {
        cout << output_stuff_idk_numbers[i] << " " << output_for_every_day[i] << '\n';
    }
}