#include <iostream>
#include <utility>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

double doubleMax = numeric_limits<double>::max();

struct Node
{
    vector<Node*> linkedNodes;
    unsigned int index;
    double prestige = doubleMax;
    bool isTraversed = false;

    explicit Node(unsigned int index) : index(index) {}

    void addLinkedNode(Node* node)
    {
        linkedNodes.push_back(node);
    }
};

vector<Node> tree;
Node* mostLinkedNode;
vector<vector<Node*>> pathByDays;

bool compareNodesLinks(const Node& n1, const Node& n2)
{
    return (n1.linkedNodes.size() > n2.linkedNodes.size());
}

bool compareNodesLinksPtrAsc(const Node* n1, const Node* n2)
{
    return (n1->linkedNodes.size() < n2->linkedNodes.size());
}

bool compareNodesIndex(const Node& n1, const Node&n2)
{
    return (n1.index < n2.index);
}

struct Input
{
    int citiesCount;
    vector<pair<int, int>> links;
    vector<int> prestiges;

    Input(int citiesCount, vector<pair<int, int>> links, vector<int> prestiges)
    {
        this->citiesCount = citiesCount;
        this->links = std::move(links);
        this->prestiges = std::move(prestiges);
    }
};

Input parseIn()
{
    ifstream inFile("taxi.in");
    int cities;
    int highways;
    vector<int> prestiges;
    vector<pair<int, int>> links;

    inFile >> cities;
    inFile >> highways;

    for(int i = cities; i > 0; i--)
    {
        int prestige;
        inFile >> prestige;
        prestiges.push_back(prestige);
        prestige = 0;
    }

    int cityA, cityB;
    while(inFile >> cityA >> cityB)
    {
        pair<int, int> link(cityA, cityB);
        links.push_back(link);
    }

    return Input(cities, links, prestiges);
}

void processLinks(const vector<pair<int, int>>& links)
{
    vector<int> linkCounts(tree.size());
    Node* firstNode;
    Node* secondNode;

    for(pair<int, int> link : links)
    {
        firstNode = &tree[link.first - 1];
        secondNode = &tree[link.second - 1];

        linkCounts[firstNode->index]++;
        linkCounts[secondNode->index]++;

        firstNode->addLinkedNode(secondNode);
        secondNode->addLinkedNode(firstNode);
    }

    for(Node& node : tree)
    {
        sort(node.linkedNodes.begin(), node.linkedNodes.end(), compareNodesLinksPtrAsc);
        if(
                node.index == distance(
                    linkCounts.begin(),
                    std::max_element(linkCounts.begin(), linkCounts.end())
                ))
        {
            mostLinkedNode = &node;
        }
    }
}

void processPrestige(vector<int> prestiges, Node* mostLinks)
{
    sort(prestiges.begin(), prestiges.end());

    int midIndex = (int)(prestiges.size() / 2);
    int mostPrestige = prestiges.at(midIndex);

    prestiges.erase(prestiges.begin()+midIndex);
    sort(tree.begin(), tree.end(), compareNodesLinks);

    for(Node& node : tree) // process ones that have no link with the most linked
    {
        if(node.prestige != doubleMax) continue;
        if(&tree[0] == &node) continue; // skip most linked (will be processed below)

        auto it = find(node.linkedNodes.begin(), node.linkedNodes.end(), mostLinks);
        if(it != node.linkedNodes.end()) continue;

        if(node.linkedNodes.size() == 1)
        {
            node.prestige = prestiges.at(midIndex); // after the erase indexes moved
            prestiges.erase(prestiges.begin()+midIndex);

            continue;
        }

        node.prestige = prestiges.back();
        prestiges.pop_back();
    }

    for(Node& node : tree)
    {
        if(node.prestige != doubleMax) continue;
        if(&tree[0] == &node) continue; // skip most linked (will be processed below)
        if(prestiges.empty()) break;

        node.prestige = prestiges.back();
        prestiges.pop_back();
    }


    sort(tree.begin(), tree.end(), compareNodesIndex);

    mostLinks->prestige = mostPrestige; // node with the most links is set with the average prestige
}

void generateTree()
{
    Input input = parseIn();


    for(int i = 0; i < input.citiesCount; i++)
    {
        tree.emplace_back(i);
    }

    processLinks(input.links);
    processPrestige(input.prestiges, mostLinkedNode);
}

vector<vector<Node*>> buildPath()
{
    vector<Node*> currentDayPath;
    Node* currentNode = &tree[0];
    bool finished = false;
    double price = 0;
    int traversedCount = 1;

    currentDayPath.push_back(&tree[0]);
    currentNode->isTraversed = true;

    while(!finished)
    {
        if(traversedCount == static_cast<int>(tree.size()))
            finished = true;

        for(Node* neighbour : currentNode->linkedNodes)
        {
            if((currentNode->linkedNodes.size() == 1 && currentNode->linkedNodes[0]->isTraversed)
                    || currentNode->linkedNodes.size() == 1)
            {
                pathByDays.emplace_back(currentDayPath);

                currentDayPath.clear();
                price = 0;
                price += pow(currentNode->prestige - neighbour->prestige, 2.0);

                currentDayPath.push_back(currentNode);

                currentNode = neighbour;

                currentDayPath.push_back(neighbour);
            }
            else {
                if (neighbour->isTraversed)
                    continue;

                currentDayPath.push_back(neighbour);

                price += pow(currentNode->prestige - neighbour->prestige, 2.0);

                currentNode = neighbour;
                neighbour->isTraversed = true;

                traversedCount++;

                break;
            }
        }
    }

    return pathByDays;
}

void generateOut()
{
    ofstream outFile("taxi.out");

    for(const Node& node : tree)
    {
        outFile << node.prestige << " ";
    }
    outFile << endl;

    outFile << pathByDays.size() << endl;

    for(vector<Node*>& path : pathByDays)
    {
        outFile << path.size() << " ";
        for(Node* city : path)
        {
            outFile << city->index + 1 << " ";
        }
        outFile << endl;
    }
}

int main()
{
    generateTree();
    buildPath();
    generateOut();

    return 0;
}