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

int GetTimeMilliseconds(const std::chrono::steady_clock::time_point& start_time,
                        const std::chrono::steady_clock::time_point& end_time) {
    return std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count();
}

std::pair<std::vector<int>, bool> TryFindColoring(std::vector<std::vector<int>>& g,
                                                  std::vector<int>& colors,
                                                  std::vector<std::unordered_set<int>>& possible_colors,
                                                  std::set<std::pair<int, int>>& possible_colors_sizes,
                                                  const std::chrono::steady_clock::time_point& start_time,
                                                  int& function_calls,
                                                  bool& time_is_up) {

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

    if (function_calls % 10000 == 0) {
        auto cur_time = std::chrono::steady_clock::now();
        auto time_diff = GetTimeMilliseconds(start_time, cur_time);

        if (time_diff > 3000) {
            time_is_up = true;
            return {{}, false};
        }
    }

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

    auto best_value = *possible_colors_sizes.begin();
    auto best_index = best_value.second;
    possible_colors_sizes.erase(possible_colors_sizes.begin());

    auto best_possible_colors = possible_colors[best_index];
    possible_colors[best_index].clear();

    for (auto possible_color : best_possible_colors) {
        colors[best_index] = possible_color;

        std::vector<int> affected_vertices;

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

        ++function_calls;
        auto result = TryFindColoring(g, colors, possible_colors, possible_colors_sizes,
                                      start_time, function_calls, time_is_up);

        if (result.second) {
            return result;
        }

        if (time_is_up) {
            return result;
        }

        colors[best_index] = 0;

        for (auto vertex : affected_vertices) {
            possible_colors_sizes.erase({possible_colors[vertex].size(), vertex});
            possible_colors[vertex].insert(possible_color);
            possible_colors_sizes.insert({possible_colors[vertex].size(), vertex});
        }
    }

    possible_colors_sizes.insert(best_value);
    possible_colors[best_index] = best_possible_colors;

    return {{}, false};
}

auto GeneratePossibleColors(std::vector<std::vector<int>>& g, 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 SolveBruteforce(std::istream& is, std::ostream& os) {
    std::vector<std::vector<int>> g;

    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 mid = (r + l) / 2;
        std::vector<int> colors_copy = colors;
        auto possible_colors_data = GeneratePossibleColors(g, colors_copy, mid);
        auto start_time = std::chrono::steady_clock::now();
        int function_calls = 1;
        bool time_is_up = false;

        auto result = TryFindColoring(g,
                                      colors_copy,
                                      possible_colors_data.first,
                                      possible_colors_data.second,
                                      start_time,
                                      function_calls,
                                      time_is_up);

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

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


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

    SolveBruteforce(std::cin, std::cout);

    return 0;
}