#include "sphinx.h"
// #include "sphinx.cpp"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

namespace {

const int CALLS_CNT_LIMIT = 2750;

int calls_cnt;

int N, M;
vector<int> C;
vector<int> X, Y;
vector<vector<int>> adj;

void quit(const char* message) {
  printf("%s\n", message);
  exit(0);
}

int count_components(const vector<int>& S) {
  int components_cnt = 0;
  vector<bool> vis(N, false);
  for (int i = 0; i < N; i++) {
    if (vis[i])
      continue;
    components_cnt++;

    queue<int> q;
    vis[i] = true;
    q.push(i);
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int nxt : adj[cur])
        if (!vis[nxt] && S[nxt] == S[cur]) {
          vis[nxt] = true;
          q.push(nxt);
        }
    }
  }
  return components_cnt;
}

} // namespace

vector<int> find_colours(int n, vector<int> x, vector<int> y){
    vector<int> ans(n);
    vector<int> e, reset(n, -1);

    int sz = 1;
    while(sz < n) sz*=2;

    if(n==2){
        e = {-1, 0};
        int x = perform_experiment(e);
        if(x == 1) ans[0] = 0;
        else ans[0] = 1;
        e = {0, -1};
        x = perform_experiment(e);
        if(x == 1) ans[1] = 0;
        else ans[1] = 1;
        return ans;
    }

    for(int i = 0; i < n;i++){
        for(int cond = 0; cond < 2;cond++){
            e = reset;
            for(int j = 0; j < n;j++){
                if(j%2==cond) e[j] = i;
            }
            int x = perform_experiment(e);
            if(x == n) continue;
            queue<array<int,6>> q;
            q.push({0, sz/2 - 1, sz/2, x, n, 0});
            while(q.size()){
                auto [l,r,v, previous_x, previous_size, tttt] = q.front();
                q.pop();
                e = reset;
                int tt = min(r, n - 1);
                for(int j = l; j <= tt;j++){
                    if(j%2 == cond) e[j] = i;
                }
                for(int j = 0; j < l;j++) e[j] = n;
                for(int j = tt + 1; j < n;j++) e[j] = n;
                if(l == tt){
                    e[tt - 1] = i;
                    e[tt] = -1;
                    x = perform_experiment(e);
                    if(x == 2) ans[l] = i;
                    continue;
                }
                x = perform_experiment(e);
                int crs = v/2;
                int add = 2 - (l == 0) - (tt == n-1);
                int current_size = tt - l + 1, current_x = x - add;

                if(tttt == 1 && current_size == current_x) continue;

                if(current_size == 2 && current_x == 1){
                    ans[l + (cond^1)] = i;
                    if(n-1!=tt) q.push({r + 1, r + v, v, previous_x, previous_size, 1});
                    continue;
                }
                
                // if it does contain all of the prev ones then we don't have to put in the other segment 
                if(current_size - current_x == previous_size - previous_x){
                    q.push({l, l + crs - 1, crs, current_x, current_size, 0});
                }
                // if the current x is equal to the size + 1 then the other segment contains everything!
                else if(current_x == current_size){
                    q.push({r + 1, r + v, v, previous_x, previous_size, 1});
                } 
                // check if the current x contains all of the previous ones, if so then we don't have to put in the other segment (only condition remaining)
                else{
                    q.push({l, l + crs - 1, crs, current_x, current_size, 0});
                    q.push({r + 1, r + v, v, previous_x, previous_size, 1});
                }
            }
        }
    }
    return ans;
}

int perform_experiment(vector<int> E) {
  calls_cnt++;
  if (calls_cnt > CALLS_CNT_LIMIT)
    quit("Too many calls");
  if ((int)E.size() != N)
    quit("Invalid argument");
  for (int i = 0; i < N; i++)
    if (!(-1 <= E[i] && E[i] <= N))
      quit("Invalid argument");

  vector<int> S(N);
  for (int i = 0; i < N; i++)
    S[i] = (E[i] == -1 ? C[i] : E[i]);

  return count_components(S);
}

int main() {
  cin >> N >> M;
  // assert(2 == scanf("%d%d", &N, &M));
  C.resize(N);
  for (int i = 0; i < N; i++) cin >> C[i];
    // assert(1 == scanf("%d", &C[i]));
  X.resize(M), Y.resize(M);
  for (int j = 0; j < M; j++) cin >> X[j] >> Y[j];
    // assert(2 == scanf("%d%d", &X[j], &Y[j]));
  // fclose(stdin);

  adj.assign(N, vector<int>());
  for (int j = 0; j < M; j++) {
    adj[X[j]].push_back(Y[j]);
    adj[Y[j]].push_back(X[j]);
  }

  calls_cnt = 0;
  vector<int> G = find_colours(N, X, Y);

  int L = G.size();
  printf("%d %d\n", L, calls_cnt);
  for (int i = 0; i < L; i++)
    printf("%s%d", (i == 0 ? "" : " "), G[i]);
  printf("\n");
  fclose(stdout);

  return 0;
}

/usr/bin/ld: /tmp/cc758g0k.o: in function `perform_experiment(std::vector<int, std::allocator<int> >)':
answer.code:(.text+0xa10): multiple definition of `perform_experiment(std::vector<int, std::allocator<int> >)'; /tmp/ccE4Vbdk.o:implementer.cpp:(.text+0x190): first defined here
/usr/bin/ld: /tmp/cc758g0k.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccE4Vbdk.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status