#include <bits/stdc++.h>
#include "sphinx.h"

using namespace std;

#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")

const ll inf = 1'000'000'000;


#ifdef lisie_bimbi
namespace {

const int CALLS_CNT_LIMIT = 2750;

int calls_cnt;

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

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

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

      std::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

int perform_experiment(std::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");

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

    return count_components(S);
}
#endif


vector<vector<int>> v;
vector<int> used;

void dfs(int u){
    used[u] = 1;
    for(auto i : v[u]){
        if(!used[i]){
            dfs(i);
        }
    }
}

vector<int> find_colours(int n, vector<int> x, vector<int> y){
    v.resize(n);
    for(int i = 0; i < n; i++){
        v[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }
    vector<int> c(n);
    for(int u = 0; u < n; u++){
        vector<int> e(n, n);
        e[u] = -1;
        used.clear();
        used.resize(n);
        used[v[u][0]] = 1;
        used[u] = 1;
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(!used[i]){
                cnt++;
                dfs(i);
            }
        }
        for(int i = 0; i < n; i++){
            e[v[u][0]] = i;
            int x = perform_experiment(e);
            if(x == cnt + 1){
                c[u] = i;
                break;
            }
        }
    }
    return c;
}

#ifdef lisie_bimbi

int main() {
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);           
#endif
    assert(2 == scanf("%d%d", &N, &M));
    C.resize(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &C[i]));
    X.resize(M), Y.resize(M);
    for (int j = 0; j < M; j++)
        assert(2 == scanf("%d%d", &X[j], &Y[j]));
    fclose(stdin);

    adj.assign(N, std::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;
    std::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;
}

#endif

/*
signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);           
#endif
    

    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
  
}
*/