#include <chrono>
#include <iostream>
#include <sstream>
#include <vector>
#include <random>
#include <set>
#include <unordered_set>

std::vector<std::vector<int>> g;

std::pair<std::vector<int>, bool> TryFindColoring(const std::vector<int>& colors,
                                 const std::vector<std::unordered_set<int>>& possible_colors,
                                 const std::set<std::pair<int, int>>& possible_colors_sizes) {

    if (possible_colors_sizes.empty()) {
        return { colors, true };
    }

    if (possible_colors_sizes.begin()->first == 0) {
        return { {}, false };
    }

    auto new_colors = colors;
    auto best_index = possible_colors_sizes.begin()->second;

    for (auto possible_color : possible_colors[best_index]) {
        new_colors[best_index] = possible_color;
        auto new_possible_colors = possible_colors;
        auto new_possible_colors_sizes = possible_colors_sizes;

        new_possible_colors[best_index].clear();
        new_possible_colors_sizes.erase(new_possible_colors_sizes.begin());

        for (auto to : g[best_index]) {
            auto it = new_possible_colors[to].find(possible_color);
            if (it != new_possible_colors[to].end()) {
                new_possible_colors_sizes.erase({new_possible_colors[to].size(), to});
                new_possible_colors[to].erase(it);
                new_possible_colors_sizes.insert({new_possible_colors[to].size(), to});
            }
        }

        auto result = TryFindColoring(new_colors, new_possible_colors, new_possible_colors_sizes);
        if (result.second) {
            return result;
        }

        new_colors[best_index] = 0;
    }

    return {{}, false};
}

auto GeneratePossibleColors(const std::vector<int>& colors, int max_color) {
    std::vector<std::unordered_set<int> > possible_colors(colors.size());
    std::set<std::pair<int, int>> possible_colors_sizes;

    for (int i = 0; i < colors.size(); ++i) {
        if (colors[i] == 0) {
            for (int j = 1; j <= max_color; ++j) {
                possible_colors[i].insert(j);
            }

            for (auto to : g[i]) {
                if (colors[to] != 0) {
                    possible_colors[i].erase(colors[to]);
                }
            }

            possible_colors_sizes.insert({possible_colors[i].size(), i});
        }
    }

    return std::make_pair(possible_colors, possible_colors_sizes);
}

void Solve(std::istream& is, std::ostream& os) {
    int n, m;
    is >> n >> m;

    g.resize(n);
    std::vector<int> colors(n);
    std::vector<std::set<int>> possible_colors(n);

    for (int i = 0; i < m; ++i) {
        int x, y;
        is >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    int max_color = 0;

    for (int i = 0; i < n; ++i) {
        is >> colors[i];
        max_color = std::max(max_color, colors[i]);
    }

    int l = max_color - 1;
    int r = n + 1;

    auto min_number_colors = n + 1;
    std::vector<int> min_coloring = {};

    while(r - l > 1) {
        int m = (r + l) / 2;
        std::cout << "Testing " << m << std::endl;
        auto possible_colors_data = GeneratePossibleColors(colors, m);
        auto result = TryFindColoring(colors, possible_colors_data.first, possible_colors_data.second);

        if (result.second) {
            if (m < min_number_colors) {
                min_number_colors = m;
                min_coloring = result.first;
            }
            r = m;
        } else {
            l = m;
        }
    }

    os << min_number_colors - max_color << std::endl;
    for (auto color : min_coloring) {
        os << color << " ";
    }
    os << std::endl;
}

template <typename Generator>
std::vector<std::pair<int, int>> GenerateRandomGraph(int vertices, int edges, Generator& gen) {
    std::vector<std::pair<int, int>> result;
    g.resize(vertices);
    int added_edges = 0;

    std::vector<std::pair<int, int>> edges_vec;
    for (int i = 0; i < vertices; ++i) {
        for (int j = i + 1; j < vertices; ++j) {
            edges_vec.emplace_back(i, j);
        }
    }

    int prev_size = edges_vec.size();

    std::uniform_int_distribution<int> distribution(0, prev_size - 1);

    while(result.size() < edges) {
        if (added_edges >= prev_size / 2) {
            std::vector<std::pair<int, int>> new_edges_vec;
            for (int i = 0; i < edges_vec.size(); ++i) {
                if (edges_vec[i] != std::pair{-1, -1}) {
                    new_edges_vec.push_back(std::move(edges_vec[i]));
                }
            }

            edges_vec = std::move(new_edges_vec);
            added_edges -= prev_size;
            prev_size = edges_vec.size();
        }

        int index = distribution(gen);
        if (edges_vec[index] == std::pair{-1, -1}) {
            continue;
        } else {
            result.push_back(edges_vec[index]);
            edges_vec[index] = {-1, -1};
            ++added_edges;
        }
    }

    return result;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::mt19937 gen(92423512);

    std::stringstream ss;

    int vertices = 10;
    int edges_num = 25;

    auto edges = GenerateRandomGraph(vertices, edges_num, gen);
    ss << vertices << " " << edges_num << "\n";
    for (auto& edge : edges) {
        ss << edge.first + 1 << " " << edge.second + 1 << "\n";
    }

    for (int i = 0; i < edges.size(); ++i) {
        ss << "0 ";
    }
    ss << "\n";

    auto start_time = std::chrono::high_resolution_clock::now();
    Solve(ss, std::cout);
    auto finish_time = std::chrono::high_resolution_clock::now();

    std::cout << vertices << " vertices " << edges_num << " edges " <<
        std::to_string(duration_cast<std::chrono::milliseconds>(finish_time - start_time).count()) << " milliseconds\n";

    return 0;
}